Futurelock : le risque subtil d’interblocage dans Rust asynchrone

• Futurelock est un phénomène d’interblocage (deadlock) qui survient lorsqu’une même tâche gère simultanément plusieurs Future, et que l’un d’eux a besoin d’une ressource détenue par un autre Future qui n’est plus sondé
• Il se produit facilement dans une instruction tokio::select! lorsque des Future référencés (&mut future) sont utilisés avec des branches contenant await
• Ce problème provient d’un échec de séparation des responsabilités entre la tâche et les Future : la même tâche attend les deux Future, mais n’en sonde plus qu’un seul, ce qui conduit à un blocage
• Des formes similaires peuvent aussi apparaître avec FuturesUnordered, les bounded channel, les Stream, etc.
• Pour une conception asynchrone sûre, l’essentiel est de séparer les Future dans des tâches distinctes avec tokio::spawn, ou d’éviter l’usage de await à l’intérieur de select

---

Concept et exemple de Futurelock

• Un Futurelock se produit lorsque la ressource détenue par le Future A est nécessaire au Future B, mais que la tâche chargée des deux Future cesse de sonder A
• Dans le code d’exemple, tokio::select! attend à la fois &mut future1 et sleep ; si sleep se termine en premier, future1 reste en attente du verrou
• Ensuite, future3 demande le même verrou, mais celui-ci est attribué à future1 ; comme future1 n’est plus sondé, le programme se fige définitivement

Interaction entre tokio::select! et Mutex

• tokio::sync::Mutex est un verrou équitable (fair), qui attribue le verrou dans l’ordre d’attente
• Le verrou est transmis à future1, mais la tâche ne sonde déjà plus que future3, donc future1 ne s’exécute pas
• Le Mutex se contente de réveiller la tâche en attente suivante, sans pouvoir savoir quel Future sera effectivement sondé

Causes générales du Futurelock

• Une structure de dépendance circulaire où la tâche T attend le Future F1, F1 dépend de F2, et F2 a de nouveau besoin que T le sonde
• Cela se produit surtout dans les situations suivantes
  • utilisation de &mut future dans tokio::select!, puis exécution d’un await dans une autre branche
  • exécution d’une autre opération asynchrone après la complétion de certains Future dans FuturesOrdered ou FuturesUnordered
  • comportement similaire dans des Future implémentés manuellement

Cas d’apparition avec les Streams et autres structures

• Dans FuturesOrdered ou FuturesUnordered, un Futurelock peut survenir si l’on retire un Future puis que l’on attend un autre Future utilisant une ressource liée à celui-ci
• join_all ne provoque pas de Futurelock, car il continue à sonder tous les Future

Cas réel et débogage

• Dans le cas Omicron#9259, tous les Future d’accès à la base de données se sont retrouvés en Futurelock, laissant les requêtes HTTP en attente infinie
• L’envoi sur un canal mpsc était bloqué, alors même que le côté réception semblait vide, ce qui compliquait l’identification de la cause
• Lors du débogage, des outils comme tokio-console peuvent aider, mais dans la plupart des cas, retracer la cause reste très difficile

Recommandations pour éviter le Futurelock

• Lorsqu’une même tâche sonde plusieurs Future, il faut veiller à ne pas interrompre le sondage d’un Future déjà démarré
• Si possible, spawn les Future dans de nouvelles tâches afin qu’ils s’exécutent indépendamment
  • transmettre un JoinHandle à tokio::select! élimine le risque de Futurelock
• Points d’attention avec tokio::select!
  • ne pas utiliser simultanément &mut future et await
  • lorsque les deux sont présents, le risque de Futurelock est élevé
• Avec des Stream, utiliser JoinSet pour exécuter chaque Future dans une tâche séparée
• Augmenter la capacité d’un bounded channel n’est pas une solution de fond
  • on peut en revanche éviter le blocage avec try_send()

Mauvaises stratégies d’évitement

• Augmenter indéfiniment la capacité du canal est irréaliste et entraîne des effets secondaires (latence, hausse de la mémoire)
• Tenter d’éliminer les dépendances entre Future reste fragile, car de nouvelles dépendances peuvent apparaître lors de la maintenance
• La seule méthode réellement sûre est la séparation en tâches via tokio::spawn

Améliorations futures et considérations de sécurité

• Possibilité d’ajouter un lint Clippy pour avertir lors de l’usage de &mut future dans tokio::select! ou en présence de await
• Le Futurelock peut être exploité sous forme de déni de service (DoS), mais comme il s’agit fondamentalement d’un dysfonctionnement, il faut surtout le prévenir

[GN⁺]

Commentaires Hacker News

• En parcourant le document, j’ai eu l’impression d’un rapport assez transparent et rigoureux
  La section des notes était particulièrement intéressante
  Il était frappant de voir que beaucoup de gens ne connaissaient pas les problèmes de cancellation safety en Rust, et qu’il est probable que ce type de problème soit répandu dans tout Omicron
  Il y a quelque chose d’ironique dans le fait d’avoir choisi Rust pour éviter les problèmes de sécurité mémoire du C, pour se retrouver cette fois avec des bugs de cancellation difficiles à attraper à l’exécution
  Le plus frustrant, c’est sans doute que le programmeur doive lui-même garantir des propriétés dynamiques que le compilateur ne peut pas aider à vérifier

  • Je me demande s’il ne faudrait pas une couche d’abstraction plus élevée pour éviter ce genre de problème
    On dirait qu’il reste malgré tout une possibilité de deadlock dans le modèle de concurrence de Rust
    On pourrait croire qu’une gestion des ressources de style RAII empêcherait ce type de situation, mais ce n’est manifestement pas le cas, ce qui est déroutant
    Je me demande si c’est juste un accident d’implémentation, ou une limite structurelle du modèle Rust/Tokio

• Cela ressemble à une variante subtile du deadlock décrit dans le billet de withoutboats sur FuturesUnordered
  Quand on utilise la concurrence “intra-task”, il faut faire attention à ce qu’aucune future ne se retrouve en famine
  En général, le plus sûr est de spawn des tasks, de gérer les timeouts avec tokio::select!, et de gérer toutes les futures en attente à l’intérieur de celui-ci
  Je ne recommande vraiment pas FuturesUnordered à moins de tester absolument tous les cas limites

• Cela fait penser à un problème d’inversion de priorité (priority inversion)
  Dans un OS, quand un thread de faible priorité détient un verrou et qu’un thread de haute priorité attend, le thread faible hérite de la priorité pour pouvoir s’exécuter
  Je me demande si un concept similaire pourrait être appliqué à Tokio — par exemple, si une future non exécutable détient un Mutex, la poll à sa place
  Cela dit, détecter l’état “non exécutable” risquerait d’avoir un coût non négligeable

  • Ce genre d’approche pourrait peut-être fonctionner au niveau des tasks dans Tokio
    Mais pas pour les futures à l’intérieur d’une task
    La conception de base de l’async Rust repose sur le fait que “futures are inert” — une future n’est qu’une simple structure, et le runtime n’a aucune visibilité sur son intérieur
    Le runtime ne connaît que les tasks, il ne suit absolument pas l’état des futures internes

  • L’async de Rust repose sur un modèle de coroutines sans pile ; il n’est donc pas sûr de reprendre arbitrairement l’exécution d’une fonction async déjà en cours
    Dans un modèle stackless, l’état local est stocké dans une pile partagée, ce qui ne permet une exécution sûre qu’en ordre LIFO
    C’est pour cela qu’il faut du coloring, et qu’on ne peut pas yield librement comme avec des coroutines avec pile

  • Le code paraît vraiment trop complexe
    C’est bien plus verbeux qu’en Erlang, Elixir, Go, ou même en C

  • Je pense que cela ressemble à un deadlock classique à deux verrous
    La file d’attente du Mutex de Tokio et l’ordonnancement des tasks s’imbriquent pour créer l’interblocage
    Avec un Mutex d’OS, on aurait pu s’en sortir en réveillant un autre thread en attente, mais en async Rust cela semble difficile à cause de la structure en machine à états des futures
    On pourrait peut-être s’en sortir en pollant séquentiellement les futures de la file d’attente, mais cela risquerait encore de produire des effets de bord inattendus

• J’ai déjà été confronté à ce genre de problème dans l’écosystème async Rust
  Interdire l’usage de références dans select! permettrait d’éviter ce type de situation, mais cela empêcherait aussi le pattern consistant à faire tourner select! de façon répétée sans perdre sa position dans la file
  Avec les problèmes de cancellation, ce genre de détail peut devenir un piège inattendu même pour des experts Rust
  Malgré tout, cela reste bien moins surprenant qu’un code basé sur des callbacks

  • Exactement, notre équipe s’est aussi demandé, après avoir analysé ce deadlock, “comment aurait-on pu l’éviter ?”, mais nous sommes arrivés à la conclusion que ce n’était la faute de personne
    Toutes les primitives de Tokio se sont comportées comme prévu, le code était correct, mais leur interaction a produit un deadlock imprévu
    On pourrait l’empêcher en interdisant &mut future dans select!, mais cela bloquerait aussi beaucoup de code parfaitement légitime
    Au final, nous en sommes arrivés à la conclusion un peu amère que c’est simplement un point sur lequel il faut être vigilant
    La discussion continue aussi dans ce commentaire

  • Si select! renvoyait les futures non sélectionnées au lieu de les drop, on pourrait éviter de perdre l’état
    Mais ce serait peu pratique, et cela ne réglerait pas le problème de fond
    La vraie cause est, comme l’explique ce fil, l’imperfection de la gestion de la cancellation

• La question de la FAQ “future1 n’est-elle pas annulée ?” était intéressante
  La cancellation se déroule en deux étapes — arrêt du poll puis drop
  Dans cet exemple, le drop est retardé, ce qui garde le guard en main et provoque des effets de bord
  Je me demande s’il serait possible de garantir que ces deux actions se produisent toujours en même temps

• J’aimerais poser la question aux concepteurs de Rust : pourquoi avoir choisi le pattern async plutôt que le modèle acteur ?
  Quand on utilise Erlang, le modèle acteur paraît beaucoup plus propre et sûr
  JavaScript était contraint d’utiliser l’async par la structure du langage, mais Rust était un nouveau langage ; je me demande donc pourquoi ce choix a été fait

  • La conception de l’async en Rust s’explique en grande partie par le support des environnements embarqués
    Il fallait que cela fonctionne sans malloc ni threads, ce qui rendait le modèle acteur impossible
    On peut écrire du code de style acteur avec Tokio, mais ce n’est pas très naturel

  • Une autre raison est la performance
    Le modèle acteur a un coût élevé de copie des messages, et Rust, en tant que langage système orienté performance, a cherché une zero-cost abstraction via des machines à états async
    Erlang et Go ont fait d’autres compromis

  • Comme Rust ne voulait pas introduire de surcoût lors des appels C FFI, un modèle basé sur des green threads a été écarté
    async/await est compilé en machine à états, avec peu d’overhead
    Go aussi a eu au départ des problèmes similaires de famine faute de préemption, avant que son scheduler ne corrige cela
    Au final, chaque langage avait des objectifs et des contraintes différents

  • J’ai moi aussi été surpris qu’Oxide adopte l’async
    C’est courant côté embarqué ou serveurs HTTP, mais je ne m’attendais pas à ce qu’une entreprise système comme Oxide l’utilise à ce point

• En lisant le document, le point que je ne comprenais pas était : pourquoi est-ce le thread principal, et non la future qui détient le verrou, qui est réveillé ?
  Avec un verrou équitable, on s’attendrait à ce que future1 soit réveillée, donc je me demande pourquoi le runtime a choisi un autre thread

• L’article était vraiment fascinant
  Le code d’exemple était clair, et même si trouver ce genre de bug doit être un cauchemar, il y a ensuite cette satisfaction de voir les pièces du puzzle s’emboîter

  • Dans notre entreprise, nous enregistrons toutes les réunions et sessions de débogage, et ce fameux “moment où le puzzle s’assemble” a justement été capturé en vidéo
    Voir Eliza, Sean, John et Dave chercher ensemble la cause lors d’un brainstorming était marquant
    Nous allons publier lundi un épisode de podcast sur le sujet
    La vidéo associée est visible dans RFD 537 et via ce lien vers l’événement

• Le fait que Rust ne fasse pas avancer simultanément toutes les tasks actives ressemble à une conception difficile à comprendre et génératrice de bugs
  L’introduction d’une structured concurrency comme dans Trio pour Python semblerait plus intuitive
  Je me demande si Rust pourrait adopter un tel modèle

  • La structured concurrency est possible en Rust, mais uniquement au niveau des tasks
    Une future n’est qu’une structure qui n’avance que lorsqu’elle est pollée, il n’existe donc pas vraiment de notion de “future active”
    Tout spawn en tasks semble résoudre le problème, mais cela empêche aussi certains patterns utiles

  • La distinction entre task et future est essentielle
    Une future ne fait rien tant qu’elle n’est pas pollée
    Si l’on définit la cancellation comme “l’état dans lequel une future n’est plus pollée tant qu’elle n’a pas été drop”, on obtient exactement le problème observé ici : une future qui s’arrête tout en gardant le verrou
    Dans la philosophie RAII de Rust, on attend du cleanup au moment du drop, mais si le poll s’arrête, même cela n’arrive pas

• Ces derniers temps, j’ai l’impression que l’async de Rust a peut-être été lancé un peu trop tôt

  • Je pense moi aussi qu’il y a beaucoup de choses à améliorer, mais le design de base reste une excellente fondation
    Pin ou certains aspects de la syntaxe peuvent être affinés, mais la structure fondamentale n’a pas besoin d’être revue
    On est encore au stade des fondations d’une maison qui n’est pas terminée, plutôt qu’à la conséquence d’une sortie précipitée
    Cela dit, je pense qu’il manque encore des couches plus basses, comme des coroutines généralisées