O processo de levar a semântica de memória transacional Verse para C++

Phil Pizlo

15 de março de 2024
Blog técnico
Engenharia
Funcionalidades
Programação
Verse
A partir da versão 28.10 do Fortnite, alguns de nossos servidores (grandes executáveis C++ baseados na Unreal Engine) são compilados com um novo compilador que oferece em C++ uma semântica de memória transacional compatível com Verse. Esse é o primeiro passo para expor ainda mais funcionalidades da Unreal Engine em Verse, preservando a semântica Verse.

A linguagem de programação Verse tem memória transacional como uma funcionalidade de primeira classe. Veja um exemplo: 

var X = 0
if:
    set X = 42      # isso é revertido por causa da
                    # linha seguinte
    X > 100         # isso falha, causando uma reversão
X = 0               # X volta a 0 devido à reversão

Esse comportamento é válido para qualquer efeito, não apenas para a operação set em Verse. Por exemplo, em vez disso, poderíamos ter chamado uma função C++, que tivesse modificado alguma variável mutável usando C++ (ou seja, armazenando em um ponteiro), e então poderíamos ter usado outras funções C++ para ler a variável mutável:

SetSomething(0)            # implementado em C++, define
                           # uma variável C++
if:
    SetSomething(42)       # isso é revertido por causa da
                           # linha seguinte
    GetSomething() > 100   # isso falha, causando uma reversão
GetSomething() = 0         # volta a 0 devido à reversão

Portanto, para haver compatibilidade com a semântica Verse adequada, precisamos que o código C++ obedeça as regras transacionais da linguagem Verse, registrando todos os efeitos para que eles possam ser revertidos.

O código Verse está sempre em execução em uma transação, e as transações são concluídas ou canceladas. As transações canceladas são "invisíveis": elas desfazem todos os efeitos, como se nada tivesse acontecido. Além das implicações para a simultaneidade, o modelo transacional da linguagem Verse diz que:
  • Um erro de tempo de execução em Verse deve cancelar toda a transação, pois a linguagem Verse não permite fazer o commit de uma transação que não foi bem-sucedida.
  • Os contextos de falha em Verse, como a condição de uma instrução if, são transações aninhadas, que passarão por commit se a condição for bem-sucedida e serão canceladas caso contrário. É permitido que as expressões condicionais tenham efeitos. Se a condição falhar, será como se os efeitos nunca tivessem acontecido.
  • Todos os efeitos são transacionalizados, mesmo aqueles que ocorrem no código nativo. Se um programa em Verse solicitar que o código C++ faça alguma coisa e, em seguida, encontrar um erro de tempo de execução na mesma transação, o que quer que o código C++ tenha feito deverá ser desfeito. Se um programa em Verse solicitar que o código C++ faça alguma coisa em um contexto de falha, e a condição falhar, o que quer que o código C++ tenha feito também deverá ser desfeito.
  • As transações em Verse são de alta granularidade Por padrão, o código Verse está sempre em uma transação, e o escopo dessa transação é determinado pelo autor da chamada mais externo em Verse. Como a maioria das APIs Verse é implementada em C++, cancelar uma transação Verse quase sempre implica ter que desfazer algumas alterações de estado do código C++.

A implementação inicial da linguagem Verse abordou essa questão da seguinte forma:
  • Deixando de lado a semântica de erro de tempo de execução Verse. Atualmente, os erros de tempo de execução Verse não revertem corretamente a transação cancelada. Precisamos corrigir isso.
  • Não permitindo que muitas APIs sejam chamadas em um contexto de falha, o que é contrário à semântica Verse. Isso aparece na linguagem como o efeito <no_rollback>, que será descontinuado assim que esse problema for corrigido.
  • Fazendo com que o código C++ compatível com transações registre manualmente os manipuladores de desfazer para todos os efeitos que ele executa. Isso é complicado o suficiente para não ser dimensionado (daí o efeito <no_rollback>) e é propenso a erros, levando a falhas difíceis de depurar, como se um manipulador de desfazer fosse registrado para algo que é excluído.

A partir da versão 28.10 do Fortnite , alguns de nossos servidores são compilados com um novo compilador C++ baseado em clang, que chamamos de AutoRTFM (Transações de Reversão Automática para Memória de Falha). Esse compilador transforma automaticamente o código C++ para registrar com precisão os manipuladores de desfazer de cada efeito (incluindo cada instrução de armazenamento), de modo que eles possam ser desfeitos no caso de uma reversão em Verse. O AutoRTFM consegue isso com zero sobrecarga de desempenho para qualquer código C++ que não esteja sendo executado em uma transação. Esse é o caso ainda que a mesma função C++ seja usada tanto em transações quanto fora delas; a sobrecarga só entra em ação quando a thread em execução está dentro do escopo de uma transação. Além disso, embora alguns códigos C++ precisem ser modificados para funcionar no AutoRTFM, só tivemos que fazer um total de 94 alterações na base de código do Fortnite para adaptá-lo ao AutoRTFM e, como mostraremos nesta publicação, mesmo essas alterações são surpreendentemente simples.

Nesta publicação, entraremos em detalhes sobre como esse compilador e seu tempo de execução funcionam e apresentaremos um pouco de nossa visão sobre como isso vai afetar o ecossistema Verse.

Compilador e tempo de execução do AutoRTFM

O AutoRTFM foi projetado para facilitar a utilização do código C++ existente, que nunca foi projetado para ter semântica transacional, e torná-lo transacional apenas com o uso de um compilador alternativo. Por exemplo, o AutoRTFM permite que você escreva códigos assim:

void Foo()
{
    TArray<int> Array = {1, 2, 3};
    AutoRTFM::Transact([&] ()
    {
        Array.Push(42);
        // Aqui a matriz é {1, 2, 3, 42}.
        AutoRTFM::Abort();
    });
    // Aqui a matriz é {1, 2, 3}, devido ao Abort.
}

Isso funciona sem nenhuma alteração no TArray. Funciona mesmo que o TArray precise realocar o armazenamento de apoio dentro do Push. O TArray não é nem mesmo especial nesse aspecto; o AutoRTFM pode fazer isso com std::vector/std::map, bem como com uma infinidade de outras estruturas de dados e funções na Unreal Engine e na biblioteca padrão C++. As únicas alterações necessárias para que isso funcione são a integração do AutoRTFM com os alocadores de memória de baixo nível e o coletor de lixo (GC), e, como mostraremos nesta seção, mesmo essas alterações são pequenas (são só aditivas e têm apenas algumas linhas; nós adicionamos as alterações a todos os vários mallocs da Unreal Engine, ao GC da Unreal Engine e ao malloc/new do sistema). E o AutoRTFM consegue isso com regressão ao desempenho zero para os caminhos de código executados fora de uma transação (portanto, fora do escopo dinâmico de uma chamada Transact). Um ponto fundamental é que, mesmo que um caminho de código (como o TArray e muitos outros) seja usado dentro de transações, os usos fora das transações não geram custo. Quando o código está sendo executado dentro de uma transação, a sobrecarga é alta (vimos 4x em alguns benchmarks internos), mas não o suficiente para prejudicar a taxa de tick do servidor do Fortnite.

Esta seção explica como isso é possível. Primeiro, descrevemos a arquitetura geral. Depois, descrevemos um novo passe do compilador LLVM, que, em vez de instrumentar o código diretamente, cria um clone transacional de todo o código que poderia participar de uma transação e, em seguida, instrumenta apenas o clone. Em seguida, descrevemos o tempo de execução e a API, que facilitam a integração do AutoRTFM ao código C++ atual (incluindo as partes mais divertidas, como os alocadores). As próximas duas seções explicam esses dois componentes.
 

Arquitetura do AutoRTFM

No longo prazo, queremos usar a memória transacional para chegar ao paralelismo. As implementações de memória transacional que alcançam o paralelismo tendem a manter um conjunto de leitura e gravação que rastreia o instantâneo do estado do heap em que a transação está sendo executada. Portanto, teríamos que instrumentar as gravações e também as leituras; caso contrário, não saberíamos se uma transação que apenas leu algum local encontrou uma corrida devido a commits simultâneos.

Mas, no curto prazo, precisamos atingir dois objetivos:
  • Semântica transacional para o código Verse, mesmo que esse código Verse faça chamadas para C++. Isso não requer paralelismo, mas requer memória transacional.
  • Normalizar a compilação do servidor do Fortnite (um trecho muito grande e maduro de código C++) com um novo compilador que adicione semântica de memória transacional.

Portanto, nossa primeira etapa não é o AutoSTM (memória transacional de software), mas sim o AutoRTFM (transações de reversão para memória de falha), que apenas implementa transações de thread única. O AutoRTFM lida com um problema estritamente mais simples. Como não há simultaneidade (já se espera que o código de jogo que a linguagem Verse chamaria seja somente de thread principal), só precisamos registrar as gravações. Ignorar as leituras significa menor sobrecarga na inicialização e menos bugs, já que qualquer código que apenas leia o heap funciona no AutoRTFM.

Conceitualmente, a arquitetura do AutoRTFM é simples. O tempo de execução do AutoRTFM mantém um registro das posições de memória e dos respectivos valores antigos. O compilador instrumenta o código para chamar funções no tempo de execução do AutoRTFM sempre que a memória é gravada. As próximas duas seções abordam os detalhes do compilador e do tempo de execução.
 

Passe do compilador LLVM

O trabalho do AutoRTFMPass é instrumentar todo o código para que ele possa obedecer a semântica transacional Verse. Mas o mesmo código no Fortnite pode ser usado em alguns lugares em que não há código Verse na pilha e a semântica Verse é desnecessária, bem como em outros lugares em que o código Verse está na pilha e uma reversão é possível.

Em vez de emitir códigos como "se a thread atual estiver na transação, então grave o registro", o compilador AutoRTFTM foi montado com base na clonagem. A representação de estar em uma transação é feita totalmente pela execução no clone transacional. Na prática, o bit bCurrentThreadIsInTransaction é codificado no contador de programa. Do ponto de vista do compilador, é simples: ele clona todo o seu código, dá nomes diferentes às funções clonadas e, em seguida, instrumenta apenas os clones. O código original continua não instrumentado e nunca faz nenhum registro nem nada de especial; portanto, a execução desse código resulta em custo zero. O código clonado recebe instrumentação e sabe que está em uma transação, o que nos permite até fazer truques semelhantes aos de uma VM, como experimentar convenções de chamadas alternativas.

Como o código é clonado, também precisamos instrumentar o código de função indireta nos clones. Se uma função realizar uma chamada indireta, o ponteiro que ela tentará chamar será um ponteiro para a versão original do receptor da chamada. Portanto, dentro do código clonado, todas as chamadas indiretas primeiro solicitam ao tempo de execução do AutoRTFM a versão clonada dessa função. Como toda a instrumentação do AutoRTFM, isso torna o código clonado mais caro, mas não tem efeito sobre o código original.

O AutoRTFMPass é executado no mesmo ponto do pipeline do LLVM que os higienizadores, ou seja, após todas as otimizações de RI terem ocorrido e antes de enviar o código para o backend. Isso tem implicações importantes, como o fato de que, mesmo nos clones instrumentados, os únicos armazenamentos e cargas que recebem instrumentação são os que sobreviveram à otimização. Portanto, embora a atribuição a uma variável local sem escape em C++ seja um "armazenamento" no sentido abstrato (e a clang representaria isso dessa forma ao criar a RI do LLVM não otimizada para esse programa), o armazenamento já terá sido totalmente eliminado até o momento em que o AutoRTFMPass fizer seu trabalho. Provavelmente, ele vai ser substituído pelo fluxo de dados SSA, com que o AutoRTFM não precisa se preocupar. Também implementamos algumas pequenas otimizações baseadas em análises estáticas de LLVM existentes para evitar a instrumentação de armazenamentos quando pudermos provar que isso não é necessário.

O uso da clonagem de funções significa que, se você compilar algum código C++ com o nosso compilador, mas nunca chamar nenhuma API de tempo de execução do AutoRTFM, os clones nunca serão invocados e, portanto, você nunca terá sobrecarga além do custo para ter um binário maior com uma grande quantidade de código morto (ou seja, não exatamente zero, mas perto disso).

A próxima seção aborda como o tempo de execução do AutoRTFM faz com que os clones instrumentados se destaquem.
 

O tempo de execução do AutoRTFM

O tempo de execução do AutoRTFM está integrado ao núcleo da Unreal Engine; portanto, do ponto de vista de um programa da Unreal Engine, como o Fortnite, ele está sempre disponível. A principal função do AutoRTFM que faz tudo acontecer é AutoRTFM::Transact. Chamar essa função com um lambda faz com que o tempo de execução configure um objeto de transação que contenha as estruturas de dados de registro e outros estados de transação. Em seguida, o Transact chama o clone do lambda. Ele é exatamente como o lambda, mas tem instrumentação transacional e obedece a ABI do AutoRTFM.

Atualmente, chamamos o Transact em resposta à entrada do código Verse em um contexto de falha, como uma condição if. No futuro, vamos chamar o Transact antes de entrar em qualquer execução de código Verse.

O tempo de execução precisa lidar com os seguintes casos e fornecer APIs para lidar com eles:
  • E se o lambda transmitido para o Transact, ou alguma função que ele chama transitivamente, não tiver um clone? Isso acontece com as funções da biblioteca do sistema, ou com qualquer função de um módulo não compilado com o AutoRTFM.
  • E se o código transacionalizado precisar realizar algum processo que não seja seguro para transações, como usar atômicas para fazer uma adição sem bloqueio de um comando a um buffer de comando de física? O AutoRTFM oferece várias APIs para assumir o controle manual da transação. A instância desse problema que costuma ser mais executada é malloc/free e funções relacionadas (como alocadores personalizados).

Sempre que o AutoRTFM receber uma solicitação para fazer uma pesquisa de função clonada, mas o clone não for encontrado, o AutoRTFM cancelará a transação com um erro. Isso garante a segurança, pois impossibilita a chamada acidental para um código não seguro para transações. Ou o receptor da chamada foi transacionalizado, e o clone está presente e é chamado, ou o receptor da chamada não foi, e você tem um cancelamento devido a uma função ausente. Portanto, chamar algo como WriteFile em uma transação é um erro por padrão. Esse é o comportamento padrão desejável, pois o WriteFile não pode ser desfeito de forma confiável. Mesmo que tentássemos desfazer a gravação mais tarde, alguma outra thread (em nosso processo ou em algum outro) poderia ter visto a gravação e realizado uma ação irrecuperável com base nisso. Sendo assim, é prático pegar um programa C++, compilá-lo com o AutoRTFM e tentar fazer um Transact. Ou ele vai funcionar corretamente, ou você vai receber um erro informando que chamou uma função não segura para transações, junto com uma mensagem sobre como encontrar essa função e seu local de chamada.

A parte mais difícil de acertar é o malloc e as funções relacionadas. O AutoRTFM adota a abordagem de não transacionalizar a implementação do malloc, mas de forçar os autores de chamada a encapsular as chamadas para o malloc com a API do AutoRTFM. Isso é especialmente simples em programas como a Unreal Engine, em que já existe uma API de fachada que encapsula a implementação real do malloc. A melhor forma de entender o que fazemos é examinar o código. Antes do AutoRTFM, o FMemory::Malloc era mais ou menos assim:
 
void* FMemory::Malloc(SIZE_T Count, uint32 Alignment)
{
    return GMalloc->Malloc(Count, Alignment);
}

Observe que removemos uma série de detalhes para mostrar apenas a parte importante.

Com o AutoRTFM, fazemos o seguinte:
 
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);
}

Vamos analisar passo a passo o que está acontecendo.
  1. Usamos UE_AUTORTFM_OPEN para dizer que o bloco delimitado (que é transformado em um lambda) deve ser executado sem instrumentação de transação. Para o tempo de execução e o compilador, isso é simples de implementar: significa apenas que emitimos uma chamada para a versão original (não clonada) do lambda. Ou seja, o GMalloc->Malloc é executado dentro da transação, mas sem nenhuma instrumentação transacional. Chamamos isso de "execução aberta" (em oposição à execução fechada, que significa executar o clone transacionalizado). Portanto, após o retorno do UE_AUTORTFM_OPEN, a chamada malloc teria sido executada até a conclusão imediatamente, sem nenhum registro de reversão. Isso mantém a semântica transacional, pois o malloc já é seguro em relação a threads, e, portanto, o fato de essa thread ter feito um malloc não é observável por outras threads até que o ponteiro para o objeto que recebeu um malloc vaze da transação. O ponteiro não vazará da transação até fazermos o commit, pois os únicos locais em que Ptr pode ser armazenado são outras memórias recém-alocadas ou a memória que o AutoRTFM transacionalizará registrando a gravação.
  2. Em seguida, registramos um manipulador de cancelamento para liberar o objeto usando AutoRTFM::OnAbort. Se a transação passar por commit, esse manipulador não vai ser executado e, portanto, o objeto que recebeu malloc vai sobreviver. Mas, se a transação for cancelada, vamos liberar o objeto. Isso garante que não haja vazamentos de memória decorrentes do cancelamento.
  3. Por fim, informamos ao AutoRTFM que esse slab de memória foi alocado recentemente, o que significa que o tempo de execução não precisa registrar gravações nessa memória. O fato de não registrar gravações na memória facilita a execução do OnAbort, pois não precisamos nos preocupar com a possibilidade de o AutoRTFM tentar sobrescrever o conteúdo do objeto de volta a algum estado anterior depois de já termos feito a liberação dele. Além disso, não registrar gravações na memória recém-alocada é uma otimização útil.

Se esse código for executado fora de uma transação (ou seja, todo esse código tiver sido chamado a partir do open), então:
  • UE_AUTORTFM_OPEN apenas executará o bloco de código.
  • AutoRTFM::OnAbort será uma instrução no-op; o lambda transmitido será simplesmente ignorado.
  • AutoRTFM::DidAllocate é uma instrução no-op.

A seguir, vamos ver o que acontece no free. Mais uma vez, removemos alguns detalhes que não são interessantes para esta discussão.

void FMemory::Free(void* Original)
{
    UE_AUTORTFM_ONCOMMIT(
    {
        GMalloc->Free(Original);
    });
}
 
A função UE_AUTORTFM_ONCOMMIT tem o seguinte comportamento:
  • Em código transacionalizado: registra um manipulador em commit para chamar o lambda fornecido abertamente. Portanto, quando e se a transação for confirmada, o objeto será liberado. A liberação não é imediata. Se a transação for cancelada, o objeto não será liberado.
  • Em código aberto: executa o lambda imediatamente, o que significa que o objeto é liberado na hora.

Esse estilo de instrumentação (a função malloc faz o malloc imediatamente, mas cancela um free, enquanto o free faz o commit do free) é aplicado a todos os nossos alocadores. O tempo de execução do AutoRTFM instala até mesmo os próprios manipuladores para malloc/free/new/delete por meio de pesquisa de função e hacks de compilador, para que você consiga o comportamento correto mesmo se usar alocadores do sistema. O GC da Unreal Engine faz algo parecido, exceto pelo fato de não haver função free, e executamos incrementos de GC no tick de fim de nível; portanto, fora de qualquer transação.

A combinação do compilador, do tempo de execução e da instrumentação malloc/GC usando as APIs Open/OnCommit/OnAbort oferece tudo que é necessário para executar o código C++ em uma transação, desde que esse código não use atômicas, bloqueios, chamadas de sistema ou chamadas para as partes da base de código da Unreal Engine que optamos por não transacionar (como os mecanismos de renderização e física, atualmente). Isso resultou em um total de 94 usos das APIs Open em todo o Fortnite. Nesses usos, ocorre o encapsulamento do código existente com o Open e correlatos na granularidade adequada, em vez da alteração de algoritmos ou estruturas de dados.

Impacto no ecossistema Verse

O AutoRTFM é a primeira etapa para expor mais semânticas Verse ao UEFN. Com o AutoRTFM, poderemos:
  • Implementar um comportamento de erro de tempo de execução mais limpo, para que um jogo possa continuar sendo executado mesmo após a ocorrência de erros. O AutoRTFM permite restaurar para um estado conhecido mesmo que o erro de tempo de execução tenha sido detectado no código C++.
  • Remover o efeito <no_rollback>, para que mais código possa ser chamado a partir de if e for. Esse efeito só existe, poluindo muitas assinaturas de funções, porque a maior parte do código C++ não pode ser transacional. O AutoRTFM corrige esse problema.
  • Expor a semântica transacional global, de modo que os acessos ao banco de dados possam ser gravados apenas como código Verse e variáveis globais. Com o AutoRTFM, o código Verse pode ser executado de forma especulativa. Isso possibilita oportunidades interessantes, como a participação do código Verse em uma transação que abrange a rede, pois poderemos fazer especulações para amortizar o custo dos acessos remotos aos dados.

Obtenha a Unreal Engine hoje mesmo!

Obtenha a ferramenta de criação mais aberta e avançada do mundo.
Com diversas funcionalidades e acesso ao código-fonte, a Unreal Engine está pronta para uso imediato.