La semántica de memoria transaccional de Verse llega a C++

Phil Pizlo

15 de marzo de 2024
A partir de la versión 28.10 de Fortnite, algunos de nuestros servidores, principalmente ejecutables de C++ grandes basados en Unreal Engine, se compilan con un nuevo compilador que confiere a C++ semántica de memoria transaccional compatible con Verse. Con ello, damos el primer paso para lograr una funcionalidad aún mayor de Unreal Engine en Verse sin dejar de lado la semántica de este último.

Una de las principales funciones del lenguaje de programación de Verse es la memoria transaccional. Pongamos un ejemplo: 

var X = 0
if:
    set X = 42      # se revierte debido a la
                    # siguiente línea
    X > 100         # falla y provoca una reversión
X = 0               # X vuelve a 0 gracias a la reversión

Este comportamiento responde a cualquier efecto, no solo a la operación set de Verse. Por ejemplo, en su lugar podríamos haber realizado una llamada a una función de C++ para modificar cualquier variable mutable mediante C++ (p. ej., guardar en un puntero) y después usar otras funciones de C++ para leer la variable mutable:

SetSomething(0)            # se implementa en C++, añade una variable
                           # C++
if:
    SetSomething(42)       # se revierte debido a
                           # la siguiente línea
    GetSomething() > 100   # falla y provoca una reversión
GetSomething() = 0         # vuelve a 0 gracias a la reversión

Por tanto, para incluir de forma adecuada la semántica de Verse, necesitamos que C++ siga las reglas transaccionales de Verse registrando todos los efectos para poder revertirlos.

El código de Verse siempre se ejecuta dentro de una transacción y estas se completan correctamente o se anulan. Estas últimas se consideran «invisibles», es decir, revierten todos sus efectos como si no hubiera ocurrido nada. Aparte de las implicaciones con respecto a la concurrencia, el modelo transaccional de Verse afirma lo siguiente:
  • Un error de ejecución de Verse debería anular toda la transacción, puesto que Verse no admite transacciones que no se hayan completado correctamente.
  • A los contextos de errores de Verse, como por ejemplo la condición de una instrucción if, se los denomina transacciones anidadas, que se confirman si dicha condición se completa correctamente o, de lo contrario, se anula. Por su parte, las expresiones condicionales admiten efectos. No obstante, si la condición falla, es como si los efectos nunca hubieran sucedido.
  • En cuanto a los efectos, todos son transaccionales, incluso aquellos que ocurren dentro del código nativo. Si un programa de Verse le pide a C++ que realice alguna acción y después se produce un error de ejecución en dicha transacción, lo que sea que haya hecho C++ debe anularse. De igual forma, si un programa de Verse le pide a C++ que realice una acción desde un contexto de error y la condición falla, lo que sea que haya hecho C++ también ha de anularse.
  • Las transacciones de Verse son de grano grueso. El código de Verse siempre se encuentra en transacción por defecto, y el alcance de dicha transacción viene determinado por el autor de la llamada a Verse más externo. Dado que la mayoría de API de Verse se implementan en C++, al anular cualquier transacción casi siempre es necesario revertir determinados cambios de estado de C++.

La implementación inicial de Verse abordó esto de la siguiente manera:
  • Excluyendo la semántica de error de ejecución de Verse. Ahora mismo, los errores de ejecución de Verse no revierten correctamente la transacción anulada, por lo que aún tenemos que solucionarlo.
  • Impidiendo que se envíen llamadas a demasiadas API en un contexto de error, al contrario que la semántica de Verse. En el lenguaje esto puede observarse en el efecto <no_rollback>, que dejaremos de usar en cuanto hayamos solucionado el problema.
  • Permitiendo que el código de C++ que admite transacciones registre de forma manual controladores de anulación para cualquier efecto que produzca. Esto es tan complicado que no se escala (de ahí el efecto <no_rollback>) y tiende a producir errores que desencadenan fallos difíciles de depurar, como si se registrara un controlador de anulación para algo que se elimina.

A partir de la versión 28.10 de Fortnite, algunos de nuestros servidores se compilan con un nuevo compilador de C++ basado en Clang, al que llamamos AutoRTFM (Transacciones de Reversión Automática para Memoria de Fallos, por sus siglas en inglés). Este transforma automáticamente el código de C++ para que registre de forma precisa controladores de anulación para cada efecto (incluyendo instrucciones de almacenamiento), de forma que se pueda anular en caso de una reversión de Verse. AutoRTFM lo logra sin sobrecargar en absoluto el rendimiento en cualquier código de C++ que no se ejecute dentro de la transacción. Esto es así incluso cuando la misma función de C++ se usa tanto en transacciones como fuera de ellas. La sobrecarga solo se produce cuando el subproceso en ejecución se encuentra dentro del alcance de la transacción. Además, si bien es necesario modificar parte del código de C++ para que se ejecute dentro de AutoRTFM, en nuestro caso solo tuvimos que realizar un total de 94 cambios en el código base de Fortnite para adaptarlo a AutoRTFM, lo cual, como veremos más adelante en la publicación, sorprende de lo simples que fueron.

En esta publicación, explicaremos con más detalle cómo funciona y se ejecuta el compilador, y os daremos nuestra opinión de cómo afectará al ecosistema de Verse.

Tiempo de ejecución y compilador de AutoRTFM

AutoRTFM está diseñado para facilitar el uso de código de C++ ya existente —que en ningún caso se creó para incluir una semántica transaccional— y convertirlo en transaccional mediante un compilador alterno. Por ejemplo, AutoRTFM permite escribir código como el siguiente:

void Foo()
{
    TArray
<int> Array = {1, 2, 3};
    AutoRTFM::Transact([&] ()
    {
        
Array.Push(42);
        // Aquí la matriz es {1, 2, 3, 42}.
        AutoRTFM::Abort();
    });
    // Aquí la matriz es {1, 2, 3} debido a Abort.


En este código, no es necesario realizar ningún cambio en TArray y funciona incluso si TArray tiene que reubicar su almacenamiento de seguridad en Push. En este sentido, TArray tampoco es especial. AutoRTFM puede hacer lo mismo tanto para std::vector/std::map como para una gran cantidad de estructuras y funciones del catálogo estándar de C++ y Unreal Engine. No obstante, los únicos cambios necesarios para que esto funcione consisten en integrar AutoRTFM en asignadores de memoria de bajo nivel y el recolector de basura (GC). Además, como veremos en este apartado, hasta esos cambios son sencillos: simplemente hay que añadir unas cuantas líneas más. De hecho, ya las hemos añadido a todas las numerosas funciones malloc y el GC de Unreal Engine, y al malloc/new del sistema). Además, AutoRTFM lo consigue con una regresión del rendimiento mínima para aquellas rutas de código que se ejecuten fuera de la transacción; es decir, fuera del ámbito dinámico de una llamada Transact. Lo más importante de todo es que, incluso cuando se usa una misma ruta de código (como TArray o muchas otras) dentro de las transacciones, aquellas que se emplean fuera de estas no conllevan ningún coste. Si bien es cierto que la sobrecarga es más alta cuando el código se ejecuta dentro de una transacción, en ocasiones hasta cuatro veces más, no es lo suficiente como para que la tasa de tic del servidor de Fortnite se vea afectada.

En este apartado se explica cómo es posible todo esto. En primer lugar, describiremos la arquitectura general. Después, explicaremos la nueva infraestructura de compiladores LLVM, que, en lugar de instrumentar el código directamente, crea un clon transaccional de todo el código que podría incluirse en una transacción y, luego, simplemente instrumenta el clon. A continuación, explicaremos el tiempo de ejecución y su API, que facilita la integración de AutoRTFM en el código de C++ existente, incluidos elementos complejos como los asignadores. En las dos secciones siguientes, explicaremos sendos componentes respectivamente.
 

Arquitectura de AutoRTFM

A largo plazo, queremos usar la memoria transaccional para lograr un paralelismo. Por lo general, este tipo de memorias con paralelismo suelen contar con una relación lectura/escritura que realiza un seguimiento del estado del montón en el que se ejecuta la transacción. De esta forma, tendríamos una herramienta que lee y escribe. De no ser así, no sabríamos si una transacción que simplemente lee una ubicación se toparía con una condición de carrera en la que se producen varias confirmaciones simultáneas.

En cualquier caso, a corto plazo queremos lograr dos objetivos principales:
  • Semántica transaccional para el código de Verse, incluso si este realiza llamadas a C++. Si bien no es necesario un paralelismo, sí lo es la memoria transaccional.
  • Normalizar la compilación del servidor de Fortnite, una parte considerable y avanzada del código de C++, con un nuevo compilador que añada la semántica de memoria transaccional.

Por lo tanto, el primer paso no se basa en AutoSTM (memoria transaccional de software), sino en AutoRTFM (transacciones de reversión para memoria de fallos), que simplemente implementa transacciones de un solo subproceso. AutoRTFM se encarga de un problema más simple. Al no haber concurrencia —se espera que el código de juego al que Verse enviaría la llamada sea solo para el subproceso principal—, basta con registrar lo que se escribe. Lo que supone omitir las lecturas es que la sobrecarga en la puesta en marcha inicial sea menor y se produzcan menos errores, puesto que el código que se encargue simplemente de leer el montón se ejecuta en AutoRTFM.

La arquitectura de AutoRTFM es muy sencilla en términos conceptuales. El tiempo de ejecución de AutoRTFM registra un historial de las ubicaciones de memoria y sus valores antiguos. El compilador instrumenta el código para que envíe llamadas a funciones en el tiempo de ejecución de AutoRTFM cada vez que se escribe la memoria. En los siguientes dos apartados analizaremos más en profundidad el compilador y el tiempo de ejecución.
 

Compilador LLVM

La función de AutoRTFMPass consiste en instrumentar todo el código para que obedezca a la semántica transaccional de Verse. No obstante, se puede usar el mismo código de Fortnite en otros lugares en los que no exista código de Verse en la pila y no sea necesaria las semántica de Verse, así como en aquellos lugares donde Verse está en la pila y es posible una reversión.

En lugar de emitir código del tipo «si el subproceso actual está en transacción, entonces escribir registro», el compilador de AutoRTFM se centra principalmente en los clones. La transacción, por su parte, se representa íntegramente al ejecutar el clon transaccional, De modo que el bCurrentThreadIsInTransaction , por tanto, se codifica en el contador de programa. En el caso del compilador, simplemente clona todo el código, asigna nombres alterados a las funciones clonadas e instrumenta solo a los clones. El código original, en cambio, se deja sin instrumentar y en ningún caso realiza algún registro ni nada especial, por lo que ejecutar dicho código no supone ningún coste. El código clonado, sin embargo, sí recibe instrumentación y es consciente de que se encuentra en una transacción, lo que nos permite trucos como los de una máquina virtual, como reproducir convenciones de llamada alternativas.

Dado que se clona el código, es necesario también instrumentar el código de función indirecta en los clones. De este modo, si una función realiza una llamada indirecta, el puntero al que intentará llamar será el puntero de la versión original del destinatario de la llamada. Así, dentro del código clonado, todas las llamadas indirectas solicitan primero al tiempo de ejecución de AutoRTFM la versión clonada de dicha función. Al igual que toda la instrumentación de AutoRTFM, esto implica que el código clonado es más costoso, pero no tiene ningún efecto sobre el código original.

AutoRTFMPass se ejecuta al mismo tiempo en la canalización de LLVM como herramientas de depuración o «sanitizer»; es decir, después de que se hayan producido todas las optimizaciones de IR e inmediatamente antes de enviar el código al back-end. Esto tiene algunas implicaciones importantes. Por ejemplo, incluso en los clones instrumentados, las únicas cargas y almacenamientos que reciben la instrumentación son aquellos que quedan de la optimización. Por tanto, si bien la asignación a una variable local sin escape en C++ se considera almacenamiento en el sentido abstracto de la palabra —y así lo representaría Clang al crear el IR de LLVM sin optimizar del programa—, dicho almacenamiento desaparecería por completo antes de que AutoRTFMPass cumpla con su función. Lo más probable es que se reemplace por el flujo de datos SSA, del que AutoRTFM no tiene que encargarse. Además, hemos implementado algunas optimizaciones mínimas basadas en los análisis estáticos de LLVM existentes para evitar la instrumentación de almacenamientos en los casos en los que se demuestre que no es necesario.

Lo que supone clonar funciones es que, si compilas código de C++ con el compilador, pero no realizas ninguna llamada a cualquier API del tiempo de ejecución de AutoRTFM, los clones nunca se invocarán. De este modo, no se producirá ninguna sobrecarga más allá del coste de tener un binario más grande con un montón de código muerto (que no es exactamente cero, pero se acerca).

En el siguiente apartado, explicaremos cómo activa a los clones instrumentados el tiempo de ejecución de AutoRTFM.
 

Tiempo de ejecución de AutoRTFM

El tiempo de ejecución de AutoRTFM se encuentra integrado en Unreal Engine Core, de modo que, en lo que respecta a programas de Unreal Engine como Fortnite, siempre está disponible. La función clave de AutoRTFM que hace posible lo imposible es AutoRTFM::Transact. Al realizar una llamada a esta función con una expresión lambda, el tiempo de ejecución crea un objeto de transacción que contiene las estructuras de datos de registro y otros estados de la transacción. Después, Transact realiza una llamada al clon de lambda, que es idéntico a la expresión lambda, pero dispone de instrumentación transaccional y obedece a la ABI de AutoRTFM.

Ahora mismo, llamamos a Transact cada vez que Verse entra en un contexto de error, como si fuera una condición If. No obstante, en el futuro, lo haremos antes de que se produzca cualquier ejecución de Verse.

El tiempo de ejecución tiene que controlar, y proporcionar API para controlar, los siguientes casos:
  • ¿Qué ocurre si la expresión lambda que ha pasado a Transact, u otra función a la que llame de forma transitiva, no tienen ningún clon? Esto sucede en el caso de funciones de la biblioteca del sistema o de cualquier función de un módulo que no se haya compilado con AutoRTFM.
  • ¿Qué sucede si el código transaccional necesita realizar alguna operación que no es recomendable para transacciones, como, por ejemplo, usar atómicos para añadir libremente un comando a un búfer de comando de físicas? AutoRTFM proporciona diversas API para controlar la transacción. En este tipo de casos, la instancia que más se ejecuta es malloc/free y otras funciones relacionadas, como asignadores personalizados.

Cada vez que se pida a AutoRTFM que busque una función clonada y no encuentre el clon, AutoRTFM cancelará la transacción con un error. De esta forma, se garantiza la seguridad, puesto que hace que sea imposible realizar llamadas por accidente a código que no sea seguro para transacciones. Si se ha transaccionalizado el destinatario y el clon está presente y recibe la llamada, o si simplemente no hay destinatario, la operación se anulará al faltar una función. De esta forma, por defecto, se producirá un error al realizar llamadas a funciones como WriteFile en una transacción. De hecho, este es el comportamiento predeterminado preferido, puesto que no existe ninguna forma fiable de revertir WriteFile. Aunque quisiéramos deshacer la escritura más tarde, algún otro subproceso (ya sea en el nuestro o en cualquier otro) podría haberla visto y realizado alguna operación irreversible según eso. Por tanto, resulta más práctico usar un programa de C++ existente, compilarlo con AutoRTFM e intentar ejecutar un Transact. En este caso, o funciona sin problemas o recibirás un error indicando que has llamado a una función no segura para transacciones junto con un aviso sobre cómo encontrar dicha función y su sitio de llamada.

Lo más complicado de todo es hacer que la función malloc y otras relacionadas funcionen correctamente. Básicamente, el enfoque que adopta AutoRTFM es el de no transaccionalizar la implementación de la función malloc, sino más bien forzar a los autores a que encapsulen las llamadas a malloc con la API de AutoRTFM. Todo esto es especialmente sencillo en programas como Unreal Engine, donde ya existe una API de fachada que encapsula la implementación de la función malloc. Para entender mejor todo esto, echemos un vistazo al código. Antes de AutoRTFM, FMemory::Malloc era algo así:
 
void* FMemory::Malloc(SIZE_T Count, uint32 Alignment)
{
    
return GMalloc->Malloc(Count, Alignment);
}


Hay que tener en cuenta que hemos eliminado algunos detalles para mostrar solo lo más importante.

En cambio, con AutoRTFM hacemos lo siguiente:
 
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);
}


Vayamos paso por paso para ver lo que ocurre.
  1. Usamos UE_AUTORTFM_OPEN para indicar que el bloque cerrado (que se convierte en una lambda) debería ejecutarse sin instrumentación de transacción. Implementar esto es sencillo en el caso del tiempo de ejecución y el compilador: basta con realizar una llamada a la versión original (sin clonar) de la función lambda. Lo que esto implica es que GMalloc->Malloc se ejecuta dentro de la transacción, pero sin ninguna instrumentación transaccional. A esto lo denominamos «ejecución abierta», frente a la ejecución cerrada, que incluye la ejecución del clon transaccionalizado. Así, cuando haya vuelto UE_AUTORTFM_OPEN, la llamada a malloc se debería completar al instante sin que se registre ninguna reversión. De esta forma, se consiguen mantener la semántica transaccional, puesto que la función malloc ya es segura para subprocesos. De igual modo, el hecho de que este subproceso haya realizado una función malloc no es observable para otros subprocesos hasta que el puntero del objeto de la malloc salga de la transacción. No obstante, el puntero no saldrá de la transacción hasta que lo confirmemos, ya que los únicos lugares donde se puede almacenar Ptr son, o bien en la nueva memoria asignada, o bien en la memoria que transaccionalizará AutoRTFM al registrar la escritura.
  2. A continuación registramos el controlador de anulación para liberar el objeto mediante AutoRTFM::OnAbort. De este modo, si la transacción se confirma, el controlador no se ejecutará, por lo que el objeto de la función malloc se mantiene. En cambio, si la transacción se anula, el objeto se liberará. Así nos aseguramos de que no se producen fugas de memoria durante la anulación.
  3. Por último, informamos a AutoRTFM de que este bloque de memoria se ha asignado hace poco, por lo que no hace falta que el tiempo de ejecución escriba en esta memoria. Al no escribir en la memoria, resulta más sencillo ejecutar OnAbort, puesto que no hay que preocuparse de que AutoRTFM intente sobrescribir el contenido del objeto a algún estado anterior a su liberación. Además, no escribir en la memoria recién asignada es una forma útil de optimización.

Si el código se ejecuta fuera de la transacción (p. ej., si recibe llamadas en abierto), ocurre lo siguiente:
  • UE_AUTORTFM_OPEN simplemente ejecuta el bloque de código.
  • AutoRTFM::OnAbort se considera una declaración no-op y simplemente se omite la lambda.
  • AutoRTFM::DidAllocate se considera una declaración no-op.

Ahora veamos qué ocurre en el caso de Free, es decir, al liberar. Aquí, al igual que en el ejemplo anterior, hemos omitido algunos detalles irrelevantes para este caso.

void FMemory::Free(void* Original)
{
  
  UE_AUTORTFM_ONCOMMIT(
    {
        
GMalloc->Free(Original);
    });
}

 
La función UE_AUTORTFM_ONCOMMIT se comporta de la siguiente manera:
  • En el caso de código transaccionalizado, esto registra un controlador de confirmación (on-commit) para realizar llamadas en abierto a la lambda en cuestión. De este modo, siempre y cuando se confirme la transacción, el objeto queda liberado, aunque no de inmediato. En cambio, si la transacción se anula, el objeto no se libera.
  • Por su parte, en código abierto, se ejecuta la lambda inmediatamente, por lo que el objeto se libera al instante.

Este estilo de instrumentación en la que Malloc ejecuta la función malloc de inmediato y aborta la declaración Free, mientras que esta última confirma Free, se aplica a todos nuestros asignadores. El tiempo de ejecución de AutoRTFM, además, instala sus propios controladores para malloc/free/new/delete mediante búsquedas de funciones y trucos del compilador. De este modo, se obtiene el comportamiento adecuado incluso con asignadores del sistema. El GC de Unreal Engine funciona de forma parecida, salvo que no cuenta con una función libre o Free, a la par que ejecutamos incrementos del GC al final del tic de nivel, es decir, fuera de cualquier transacción.

La combinación del compilador, el tiempo de ejecución y la instrumentación malloc/GC mediante API Open/OnCommit/OnAbort nos proporciona todo lo necesario para ejecutar código C++ en una transacción, siempre y cuando este no use atómicos, bloqueos, llamadas al sistema o llamadas a partes del código base de Unreal Engine que hemos optado por no transaccionalizar (como motores físicos o de renderización, en nuestro caso). Esto ha supuesto un total de 94 usos de las API Open en todo Fortnite. Lo que implican dichos usos es encapsular el código existente con Open y similares con la granularidad adecuada en lugar de modificar algoritmos y estructuras de datos.

Impacto sobre el ecosistema de Verse

Con AutoRTFM, damos un primer paso para conseguir llevar muchas más semánticas de Verse a UEFN. Esto nos permitirá:
  • Implementar un comportamiento de error de tiempo de ejecución más limpio, para que el juego siga funcionando incluso después de producirse errores. AutoRTFM permite restablecer un estado conocido incluso cuando se ha detectado un error en pleno código de C++.
  • Eliminar el efecto <no_rollback>, de modo que se puedan enviar llamadas a más código desde if y for. La razón de que dicho efecto se encuentre ahí, contaminando multitud de firmas de función, radica en que la mayoría del código de C++ no puede ser transaccional. Con AutoRTFM, eso ya no es un problema.
  • Exponer la semántica transaccional global, de forma que los accesos a la base de datos se puedan escribir solo como código de Verse o como variables globales. AutoRTFM permite que el código de Verse se pueda ejecutar de forma especulativa. Esto da pie a multitud de posibilidades interesantes, como que Verse participe en una transacción que abarque la red, puesto que podremos realizar especulaciones para amortizar el coste de accesos remotos a los datos.

¡Hazte ya con Unreal Engine!

Consigue la herramienta de creación más abierta y avanzada del mundo.
Unreal Engine incluye todas las funciones y acceso ilimitado al código fuente, ¡listo para usar!