Importer la sémantique de mémoire transactionnelle de Verse dans C++

Phil Pizlo

15 mars 2024

Depuis la version 28.10 de Fortnite, certains de nos serveurs (de gros exécutables en C++ s'appuyant sur l'Unreal Engine) sont compilés avec un nouveau compilateur qui dote le C++ d'une nouvelle sémantique de mémoire transactionnelle compatible avec Verse. Il s'agit d'une première étape de notre projet qui consiste à exposer plus de fonctionnalités de l'Unreal Engine dans Verse tout en préservant la sémantique de Verse.

Dans le langage de programmation Verse, la mémoire transactionnelle est une fonction de première classe. Voici un exemple :

var X = 0
if:
set X = 42 # ceci est annulé en raison de
# la prochaine ligne
X > 100 # ceci échoue et entraîne une annulation
X = 0 # X revient à 0 grâce à l'annulation

Ce comportement s'applique à tous les effets, pas uniquement à l'opération set dans Verse. Nous aurions pu par exemple appeler une fonction C++, qui modifiait une variable mutable avec C++ (en l'entreposant dans un pointeur), avant d'utiliser d'autres fonctions C++ pour lire cette variable mutable :

SetSomething(0)            # implémenté en C++, définit
             # une variable C++
if:
    SetSomething(42)       # ceci est annulé en raison de
             # la prochaine ligne
    GetSomething() > 100   # ceci échoue et entraîne une annulation
GetSomething() = 0         # revient à 0 grâce à l'annulation

Ainsi, pour que la sémantique de Verse soit correctement prise en charge, C++ doit respecter les règles transactionnelles de Verse en enregistrant tous les effets afin de pouvoir les annuler.

Le code Verse s'exécute toujours avec des transactions qui aboutissent ou sont annulées. Les transactions annulées sont "invisibles" : elles annulent tous leurs effets, comme si rien ne s'était passé. Outre les conséquences en termes de simultanéité, voici ce qui caractérise le modèle transactionnel de Verse :

Une erreur d'exécution dans Verse devrait annuler la transaction au complet, puisque Verse n'autorise pas les transactions qui n'ont pas abouti.
Les contextes d'échec de Verse (tels que la condition d'une instruction if) sont des transactions imbriquées qui sont validées si la condition est remplie, mais s'annulent dans le cas inverse. Les expressions conditionnelles peuvent avoir des effets. Si la condition échoue, c'est comme si les effets n'avaient jamais eu lieu.
Tous les effets sont rendus transactionnels, même ceux qui s'exécutent en code natif. Si un programme Verse demande au C++ d'effectuer une action et qu'une erreur d'exécution a lieu dans la même transaction, tout ce qu'aura fait le C++ devra être annulé. Si un programme Verse demande au C++ d'effectuer une action dans un contexte d'échec et que la condition échoue, tout ce qu'aura fait le C++ devra aussi être annulé.
Les transactions de Verse sont peu détaillées. Par défaut, le code Verse est toujours dans une transaction par défaut et l'étendue de cette dernière est déterminée par l'appelant le plus distant dans Verse. Puisque la plupart des API Verse sont implémentées en C++, l'interruption d'une transaction Verse implique presque systématiquement de devoir annuler des changements d'état en C++.

Voici comment le problème était corrigé dans la première implémentation de Verse :

En ignorant la sémantique des erreurs d'exécution de Verse. À l'heure actuelle, les erreurs d'exécution de Verse n'annulent pas correctement la transaction interrompue. Nous devons corriger ce problème.
En empêchant de nombreuses API d'être appelées dans un contexte d'échec, contrairement à la sémantique de Verse. Dans le langage, cela correspond à l'effet <no_rollback>, qui deviendra obsolète dès que le problème sera résolu.
En ayant du code C++ qui prend en charge les transactions et enregistre manuellement les gestionnaires d'annulation pour tous les effets qu'il exécute. Une solution compliquée puisqu'il ne s'adapte pas (d'où l'effet <no_rollback>) et entraîne des plantages difficiles à déboguer, comme quand un gestionnaire d'annulation est enregistré pour une action qui est supprimée.

Depuis la version 28.10 de Fortnite, certains de nos serveurs sont compilés avec un nouveau compilateur C++ s'appuyant sur Clang, appelé AutoRTFM (pour "Automatic Rollback Transactions for Failure Memory"). Ce compilateur convertit automatiquement le code C++ afin d'enregistrer précisément les gestionnaires d'annulation pour chaque effet (y compris les instructions de stockage), pour qu'ils puissent être annulés en cas de rollback de Verse. Il y parvient sans aucun coût de performance vers n'importe quel code C++ qui n'est pas exécuté dans une transaction. Cela fonctionne même si une fonction C++ est utilisée à la fois dans des transactions et en dehors. Le coût de performance n'apparaît que lorsque le thread d'exécution est compris dans l'étendue d'une transaction. De plus, bien qu'il faille modifier certaines données du code C++ afin qu'il fonctionne dans AutoRTFM, nous n'avons eu à effectuer que 94 changements au total dans la base de code de Fortnite pour l'adapter à AutoRTFM. Et comme vous allez le voir dans cet article, ils sont extrêmement simples.

Dans cet article, nous allons exposer en détail le fonctionnement de ce compilateur et de son exécution, et vous donner un aperçu de l'impact qu'ils auront sur l'écosystème Verse selon nous.

Le compilateur AutoRTFM et son exécution

AutoRTFM a été conçu pour rendre transactionnel du code C++ qui n'a, à la base, pas vocation à avoir une sémantique transactionnelle, et ce simplement en utilisant un compilateur alternatif. AutoRTFM vous permet par exemple d'écrire le code suivant :

void Foo

()

{

    TArray

<int> Array = {1, 2, 3};
AutoRTFM::Transact([&] ()

Array.Push(42);
        // Ici la matrice est {1, 2, 3, 42}.
        AutoRTFM::Abort();
    });
    // Ici la matrice est {1, 2, 3} en raison d'Abort.
}

Cela fonctionne sans apporter aucun changement à TArray. Cela fonctionne même si TArray doit réallouer son stockage dans Push. TArray n'est en rien une exception. AutoRTFM peut faire la même chose pour std::vector/std::map et de nombreuses autres structures de données et fonctions de l'Unreal Engine et de la bibliothèque standard C++. Les seuls changements nécessaires pour que cela fonctionne sont l'intégration à AutoRTFM d'allocateurs de mémoire de bas niveau et le nettoyage de mémoire (GC), et comme nous le verrons dans cette partie, ce sont des changements mineurs (il s'agit de l'ajout d'une poignée de lignes que nous avons ajoutées aux nombreux malloc de l'UE, à son nettoyage de mémoire, et à la fonction malloc et à l'opérateur new du système). Qui plus est, AutoRTFM effectue l'opération sans aucune perte de performances pour les chemins de code qui s'exécutent hors transaction (donc en dehors de l'étendue dynamique d'un appel Transact ). En résumé, même si un chemin de code (comme TArray entre autres) est utilisé à l'intérieur de transactions, ceux qui sont utilisés en dehors des transactions n'engendrent pas de coût. Quand du code s'exécute dans une transaction, le coût en performances est élevé (jusqu'à 4 fois plus élevé d'après nos tests de performances réalisés en interne), mais pas suffisamment pour impacter la vitesse de ticks du serveur de Fortnite.

La partie suivante explique comment nous sommes parvenus à ce résultat. Nous y décrivons tout d'abord l'architecture globale. Ensuite, nous décrivons la nouvelle passe du compilateur LLVM qui, plutôt que d'instrumenter directement le code, crée un clone transactionnel de tout le code qui pourrait potentiellement prendre part à une transaction, et n'instrumente que celui-ci. Enfin, nous décrivons l'exécution et son API, qui facilitent l'intégration d'AutoRTFM dans le code C++ existant (dont les éléments les plus sympas, comme les allocateurs). Les deux parties suivantes expliquent respectivement ces composants.

L'architecture AutoRTFM

À long terme, nous voulons utiliser la mémoire transactionnelle pour atteindre le parallélisme. Les implémentations de mémoire transactionnelle qui atteignent le parallélisme conservent généralement une liste de lecture-écriture, qui suit la capture de l'état de la pile dans laquelle la transaction s'exécute. Il nous faudrait ainsi instrumenter à la fois les données d'écriture et de lecture, sans quoi nous ne serions pas en mesure de savoir si une transaction qui a uniquement lu un emplacement s'est heurtée à une situation de compétition provoquée par des validations simultanées.

Nous avons deux objectifs à court terme :

Intégrer la sémantique transactionnelle au code Verse, même si ce dernier fait appel à du C++. Cela ne nécessite pas le parallélisme, mais nécessite en revanche la mémoire transactionnelle.
Normaliser la compilation du serveur de Fortnite, un fragment de code C++ volumineux et avancé, avec un nouveau compilateur offrant la sémantique de mémoire transactionnelle.

Notre première étape n'est donc pas AutoSTM (Software Transactional Memory), mais AutoRTFM (Rollback Transactions for Failure Memory), qui implémente simplement des transactions mono-thread. AutoRTFM gère un problème beaucoup plus simple. Puisqu'il n'y a pas de simultanéité (le code de gameplay que Verse appellerait repose déjà sur un thread principal), il suffit d'enregistrer les données d'écriture. Ignorer les données de lecture réduit le coût en performance lors du chargement initial ainsi que les bugs, puisque le code qui lit la pile fonctionne dans AutoRTFM.

Le modèle architectural d'AutoRTFM est simple. L'exécution d'AutoRTFM tient un journal d'emplacements mémoire et de leurs anciennes valeurs. Le compilateur instrumente du code pour appeler des fonctions pendant l'exécution d'AutoRTFM à chaque fois qu'on écrit en mémoire. Les deux prochaines parties décrivent en détail le compilateur et son exécution.

Passe du compilateur LLVM

Le rôle d'AutoRTFMPass est d'instrumenter tout le code pour qu'il obéisse à la sémantique transactionnelle de Verse. Mais dans Fortnite, le même code peut être utilisé à des endroits où il n'y a pas de code Verse dans la pile et où la sémantique Verse est donc inutile, ou encore à des endroits où du code Verse est dans la pile et où une annulation est possible.

Plutôt que d'émettre du code comme "si le thread actuel fait partie d'une transaction, alors écrire dans le journal", le compilateur AutoRTFM s'appuie sur le clonage. L'appartenance à une transaction est représentée exclusivement par l'exécution dans le clone transactionnel. Dans les faits, l'information bCurrentThreadIsInTransaction est encodée dans le compteur ordinal. Le rôle du compilateur est simple : il clone l'intégralité de votre code, attribue des noms décorés aux fonctions clonées et n'instrumente ensuite que les clones. Le code d'origine n'est jamais instrumenté, consigné dans un journal ou soumis à une autre action spécifique, et son exécution n'engendre donc aucun coût. Le code cloné bénéficie de l'instrumentation et sait qu'il fait partie d'une transaction, ce qui nous permet même d'appliquer des astuces de machine virtuelle, comme jouer avec des conventions de nommage différentes.

Puisque le code est cloné, nous devons également instrumenter du code de fonction dans les clones. Si une fonction effectue un appel indirect, le pointeur qu'elle essaiera d'appeler renverra vers la version d'origine de l'appelé. Donc, à l'intérieur du code cloné, tous les appels indirects commencent par demander la version clonée de la fonction à l'exécution d'AutoRTFM. Comme toute l'instrumentation d'AutoRTFM, cela rend le code cloné plus coûteux, mais n'a aucun effet sur le code d'origine.

AutoRTFMPass s'exécute au même moment dans le pipeline LLVM que les assainisseurs : après les optimisations de représentation intermédiaire et juste avant l'envoi du code au back-end. Ceci a des répercussions importantes, comme le fait que même dans les clones instrumentés, seuls les charges et les stockages qui ont survécu à l'optimisation bénéficient de l'instrumentation. Ainsi, si l'assignation à une variable locale de non-échappement en C++ peut être qualifiée de "stockage" au sens abstrait (et Clang le représenterait de cette façon lors de la création de la représentation intermédiaire LLVM non optimisée pour ce programme), le stockage aurait totalement disparu au moment où AutoRTFMPass agirait. Il serait sans doute remplacé par un flux de données SSA auquel AutoRTFM n'a pas besoin de toucher. Nous avons également implémenté quelques optimisations s'appuyant sur des analyses statiques LLVM existantes pour éviter d'instrumenter des stockages quand cela n'est pas nécessaire.

Grâce au clonage de fonction, si vous compilez du code C++ avec notre compilateur, mais que vous ne faites jamais appel à une API d'exécution AutoRTFM, alors les clones ne seront jamais appelés et les coûts en performances se limiteront aux coûts inhérents à un binaire volumineux contenant du code mort (donc des coûts proches de zéro).

La partie suivante explique comment l'exécution d'AutoRTFM exploite les clones instrumentés.

L'exécution d'AutoRTFM

L'exécution d'AutoRTFM est intégrée au noyau de l'Unreal Engine, elle est donc toujours disponible aux programmes de l'UE tels que Fortnite. La fonction clé d'AutoRTFM qui rend tout cela possible est AutoRTFM::Transact. En appelant cette fonction avec une lambda, l'exécution établit un objet de transaction qui contient les structures de données du journal ainsi que d'autres états de transaction. Transact appelle ensuite le clone de la lambda. Il est parfaitement identique à la lambda, mais bénéficie de l'instrumentation transactionnelle et obéit à l'API AutoRTFM.

À l'heure actuelle, nous appelons Transact quand Verse entre dans un contexte d'échec, comme une condition "if". À l'avenir, nous appellerons Transact avant toute exécution de Verse.

L'exécution doit gérer et fournir des API pour gérer les situations suivantes :

Que se passe-t-il si la lambda transmise à Transact (ou une fonction appelée de manière transitive) n'a pas de clone ? C'est ce qui arrive avec les fonctions de bibliothèque du système ou toute fonction provenant d'un module qui n'est pas compilé avec AutoRTFM.
Que se passe-t-il si le code rendu transactionnel doit effectuer une action qui n'est pas transaction-safe, comme utiliser une opération atomique pour ajouter une commande sans verrou à un tampon de commande physique ? AutoRTFM fournit plusieurs API pour prendre le contrôle manuel des transactions. L'instance problématique exécutée la plus courante est la fonction malloc/free et les fonctions liées (comme les allocateurs personnalisés).

Lorsqu'AutoRTFM reçoit une demande de recherche de fonction clonée et qu'il ne trouve pas de clone, il annule la transaction et génère une erreur. La sécurité est ainsi garantie puisqu'il est dès lors impossible d'appeler accidentellement du code qui n'est pas transaction-safe. Soit l'appelé a été rendu transactionnel et le clone existe et peut être appelé, soit il ne l'a pas été et l'opération est interrompue due à une fonction manquante. Appeler une fonction comme WriteFile dans une transaction est donc une erreur par défaut. C'est un comportement par défaut souhaitable, puisque WriteFile ne peut pas être annulé de façon fiable. Nous aurions beau essayer d'annuler l'écriture ultérieurement, un autre thread (dans notre processus ou un autre) aurait pu assister à l'écriture et effectuer une action irrécupérable en conséquence. Il est donc pratique de prendre un programme C++ existant, de le compiler avec AutoRTFM et d'essayer d'effectuer un Transact. Soit l'opération fonctionnera, soit vous obtiendrez une erreur indiquant que vous avez appelé une fonction non transaction-safe ainsi qu'un message expliquant comment trouver cette fonction et son site d'appel.

La partie la plus difficile à maîtriser est malloc et ses fonctions reliées. AutoRTFM prend le parti de ne pas rendre l'implémentation de malloc transactionnelle, mais de forcer les appelants à englober les appels à malloc avec l'API AutoRTFM. C'est d'autant plus simple dans des programmes comme l'Unreal Engine, où une API de façade s'occupe déjà d'englober l'implémentation de malloc. Pour mieux comprendre ces actions, regardons le code. Avant AutoRTFM, FMemory::Malloc ressemblait à ceci :

void* FMemory::Malloc(SIZE_T Count, uint32 Alignment

)

{

return GMalloc->Malloc

(Count, Alignment);

}

À noter que nous avons supprimé certains détails pour ne conserver que l'essentiel.

Voici comment nous procédons avec AutoRTFM :

void* FMemory::Malloc(SIZE_T Count, uint32 Alignment

)

{

void*

 Ptr;

UE_AUTORTFM_OPEN

(

    {

        Ptr =

GMalloc->Malloc

(Count, Alignment);

    });

    AutoRTFM::

OnAbort([Ptr

]

    {

Free

(Ptr);

    });

return AutoRTFM::DidAllocate

(Ptr, Count);

}

Analysons chaque étape du processus.

Nous utilisons UE_AUTORTFM_OPEN pour déclarer que le bloc délimité (qui est converti en lambda) doit s'exécuter sans instrumentation de transaction. C'est une fonction simple à implémenter pour l'exécution et le compilateur : elle signifie juste que nous lançons un appel vers la version d'origine (non clonée) de la lambda. GMalloc->Malloc s'exécute donc dans la transaction, mais sans instrumentation transactionnelle. Nous appelons cela l'"exécution du code ouvert" (par opposition à l'"exécution du code fermé", qui désigne l'exécution du clone rendu transactionnel). Après le retour de UE_AUTORTFM_OPEN, l'appel de malloc doit s'être exécuté immédiatement jusqu'au bout sans qu'aucune annulation n'ait été enregistrée. On conserve ainsi la sémantique transactionnelle, car malloc est déjà thread-safe, et le fait que ce thread ait effectué un malloc n'est pas observable par les autres threads avant que le pointeur vers l'objet visé par l'allocation de mémoire fuie de la transaction. Le pointeur ne fuira pas de la transaction tant que nous n'aurons pas validé, puisque les seuls endroits où Ptr peut être stocké sont soit une autre mémoire nouvellement allouée, soit une mémoire qu'AutoRTFM rendra transactionnelle en consignant l'écriture.
Nous enregistrons ensuite un gestionnaire d'annulation pour libérer l'objet qui utilise AutoRTFM::OnAbort. Si la transaction est validée, ce gestionnaire ne s'exécute pas et l'objet visé par malloc survit. Mais si la transaction est interrompue, l'objet est libéré. Cela garantit que l'abandon n'engendre pas de fuite de mémoire.
Enfin, nous informons AutoRTFM que cette portion de mémoire est nouvellement allouée, ce qui signifie que l'exécution n'a pas à y consigner l'écriture. Le fait de ne pas consigner l'écriture dans la mémoire facilite l'exécution de OnAbort, puisque nous n'avons pas à craindre qu'AutoRTFM essaie d'écraser le contenu de l'objet pour revenir à un état précédent alors que nous l'avons déjà libéré. De plus, il s'agit d'une optimisation utile.

Si ce code s'exécute en dehors d'une transaction (c'est-à-dire s'il a été appelé depuis le code ouvert), alors :

UE_AUTORTFM_OPEN exécute uniquement le bloc de code.
AutoRTFM::OnAbort est une no-op (une instruction nulle) ; la lambda transmise est ignorée.
AutoRTFM::DidAllocate est une no-op.

Voyons maintenant ce qu'il se passe à l'étape de libération "free". Là encore, nous avons omis des détails qui ne présentaient pas d'intérêt dans le cadre de cette discussion.

void FMemory::Free(void* Original

)

{

UE_AUTORTFM_ONCOMMIT

(

    {

GMalloc->Free

(Original);

    });

}

La fonction UE_AUTORTFM_ONCOMMIT a le comportement suivant :

En code rendu transactionnel : elle enregistre un gestionnaire de validation qui appelle la lambda donnée dans le code ouvert. Donc, si et quand la transaction est validée, l'objet est libéré. Il n'est pas libéré immédiatement. Si la transaction est interrompue, il n'est pas libéré.
En code ouvert : elle exécute la lambda immédiatement et l'objet est libéré immédiatement.

Le style d'instrumentation (l'allocation de mémoire se fait immédiatement, l'objet n'est pas libéré quand la transaction échoue, mais il est libéré quand elle est validée) est appliqué à tous nos allocateurs. L'exécution d'AutoRTFM installe même ses propres gestionnaires pour malloc/free/new/delete via la recherche de fonction et des astuces du compilateur, donc vous obtiendrez le bon comportement même si vous utilisez des allocateurs système. Le nettoyage de mémoire de l'Unreal Engine fonctionne de la même façon, sauf qu'il n'y a pas de fonction "free" et que nous exécutons ses incrémentations à la fin du tick de niveau, donc en dehors de toute transaction.

En combinant compilateur, exécution et instrumentation de malloc/nettoyage de mémoire via les API Open/OnCommit/OnAbort, nous disposons de tout ce dont nous avons besoin pour exécuter du code C++ dans une transaction, tant que ce code n'utilise pas d'opérations atomiques, de verrous, d'appels système ou d'appels vers des parties de la base de code de l'UE que nous avons choisi de ne pas rendre transactionnelles (comme les moteurs de rendu et physique, à l'heure actuelle). Au total, cela a engendré 94 utilisations des API Open dans tout Fortnite. Nous avons notamment englobé du code existant avec Open et consorts au bon niveau de granularité plutôt que de modifier les algorithmes ou les structures de données.

L'impact de l'écosystème Verse

AutoRTFM constitue la première étape pour exposer plus de sémantique Verse dans l'UEFN. Avec AutoRTFM, nous allons pouvoir :

Améliorer la gestion des erreurs d'exécution de manière à ce qu'un jeu continue de tourner même après une erreur. En effet, AutoRTFM nous permet de revenir à un état connu même si l'erreur d'exécution a été détectée au plus profond du code C++.
Supprimer l'effet <no_rollback> afin que plus de code puisse être appelé avec les fonctions if et for. Cet effet (qui pollue de nombreuses signatures de fonction) existe uniquement, car une grande partie du code C++ ne peut pas être transactionnelle. Mais AutoRTFM résout ce problème.
Exposer la sémantique transactionnelle globale afin que les accès à la base de données puissent être écrits uniquement en code Verse et en variables globales. Grâce à AutoRTFM, le code Verse peut s'exécuter de façon spéculative. Cela crée des opportunités intéressantes, comme le fait de pouvoir inclure Verse dans une transaction qui étend le réseau, puisque nous allons pouvoir spéculer pour amortir le coût des accès aux données à distance.

Obtenez l'Unreal Engine dès maintenant !

Procurez-vous l'outil de création le plus ouvert et le plus avancé au monde.
L'Unreal Engine est prêt à l'emploi, avec toutes les fonctionnalités et un accès complet au code source.