Operações atômicas em

Sobre Operações atômicas

Uma única instrução pode parecer uma ação indivisível, mas não é nada disso. Veja o caso de somar cinco a um valor na memória:

add qword [rel counter], 5

Por baixo dos panos, o processador não consegue somar diretamente na memória. Ele quebra essa única instrução em três passos menores, chamados micro-operações:

1. ler o valor atual da memória;
2. modificar esse valor em um registrador, somando cinco a ele;
3. escrever o resultado de volta.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

Esse é um padrão comum chamado read-modify-write (RMW).

Repare que a leitura (ou load) e a escrita (ou store) são eventos separados, então existe uma janela de tempo entre eles. Normalmente não percebemos isso porque, em um único núcleo, cada instrução tem a garantia de produzir seu efeito por completo antes da próxima. Essa janela, portanto, é invisível, e add se comporta como uma única unidade.

No entanto, CPUs modernas raramente têm um único núcleo, e os aplicativos costumam rodar em vários núcleos ao mesmo tempo, sem sequenciamento entre eles. Com vários núcleos rodando no mesmo instante, outro núcleo pode ler ou escrever counter dentro dessa janela, depois do load deste núcleo e antes do store. Duas threads fazem load do mesmo valor antigo, cada uma soma cinco, e cada uma faz store do seu resultado. Duas adições aconteceram, mas o valor só avançou cinco. Uma atualização foi perdida silenciosamente.

Isso é uma corrida de dados, e é um problema comum em código multithread.

Nem todo valor fica exposto dessa forma. Cada thread tem seus próprios registradores e sua própria pilha, então um valor mantido em um registrador, ou uma variável local na pilha de uma thread, é exclusivo daquela thread e não pode sofrer corrida. Só a memória compartilhada entre as threads, como counter acima, precisa de proteção.

O x86-64 oferece um conjunto de instruções para resolver esse problema, tornando uma instrução indivisível. Ela se comporta como uma única unidade não só para o núcleo que a processa, mas também para todos os outros núcleos. Uma operação que se mantém íntegra, que nenhum outro núcleo consegue dividir, é chamada de atômica.

Troca Atômica

A instrução xchg troca dois operandos. O operando de destino passa a ser igual ao valor anterior do operando de origem, enquanto o operando de origem passa a ser igual ao valor anterior do operando de destino. Conceitualmente, pode ser vista como duas instruções mov acontecendo ao mesmo tempo.

Como de costume, pode ser usada com dois operandos de registrador ou com um operando de memória e um operando de registrador:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Quando usada com um operando de memória, xchg é sempre atômica. O processador mantém um lock sobre a posição durante toda a operação, o mesmo mecanismo que o prefixo lock usa para outras instruções, descrito a seguir.

O prefixo lock

A forma mais comum de tornar uma instrução atômica no x86-64 é adicionar o prefixo lock. Ele funde a leitura, a modificação e a escrita em um único passo indivisível. Isso significa que o núcleo mantém a memória com exclusividade durante todo o processo, de modo que nenhum outro núcleo pode ler ou escrever nessa posição no meio do caminho.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock só funciona quando o destino é a memória, e apenas em instruções que fazem read-modify-write nessa memória:

1. operações aritméticas, como add, sub, inc, dec, neg;
2. operações bit a bit, como and, or, xor, not;
3. as operações de bits bts, btr, btc;
4. algumas outras instruções dedicadas, como xadd e cmpxchg, descritas abaixo.

Em qualquer outra instrução, como um mov simples, o prefixo é inválido e o processador gera uma falha de opcode inválido. Um load ou um store isolado não precisa de prefixo: um acesso naturalmente alinhado já é atômico por si só.

Operações Atômicas com Bits

Entre as instruções que aceitam lock, os testes de bits combinam naturalmente com o spinlock do fim deste documento. Cada uma de bts, btr e btc copia um bit escolhido para a flag de carry e depois o define, limpa ou inverte. Com o prefixo lock, isso vira um read-modify-write de um bit: o bit é alterado atomicamente, e CF informa qual era o valor anterior.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

Uma definição que encontra o bit já definido significa que outra thread o reivindicou primeiro. Essa é a versão de um único bit da reivindicação de flag que xchg faz para uma palavra inteira.

Troca e Soma

Um lock add simples atualiza a memória, mas joga fora o valor antigo. Muitas vezes o valor antigo é exatamente o que se quer, por exemplo para dar a cada thread um número de senha distinto.

A instrução xadd (x de exchange) retorna o valor anterior enquanto soma. Ela escreve a soma no destino e deixa o valor original do destino no registrador de origem.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Com o prefixo lock, isso é um fetch-and-add atômico. Executado por muitas threads no mesmo contador, cada chamada retorna um valor antigo diferente.

Assim como no lock add, o contador termina exatamente no número de chamadas. No entanto, ao contrário do lock add, todo valor intermediário também é retornado, um para cada chamador.

A origem pode ser qualquer registrador de uso geral, e a largura do operando vai de um byte a um quadword. Somar um valor negativo transforma a mesma instrução em um fetch-and-subtract.

Comparação e Troca

xadd soma e xchg sobrescreve, mas nenhuma das duas consegue fazer o novo valor depender do valor atual e aplicá-lo só se nada tiver mudado por baixo. Essa atualização condicional é o que cmpxchg, compare-and-exchange, proporciona, e é a mais geral dessas primitivas.

cmpxchg dest, src usa rax como acumulador implícito e o compara com dest:

• Se dest == rax, então dest = src e ZF = 1.
• Se dest != rax, então rax = dest e ZF = 0.

O acumulador acompanha o tamanho do operando: al para um byte, depois ax, eax e rax para as formas mais largas.

Repare que dest só é atualizado quando é igual ao valor esperado, previamente carregado em rax. Essa igualdade garante que dest ainda contém o valor a partir do qual o novo foi calculado, então uma atualização baseada em uma leitura desatualizada nunca é aplicada. Isso faz do cmpxchg o bloco de construção de uma atualização atômica, também conhecida como compare-and-swap (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Esse laço de repetição é o coração das atualizações sem lock. A janela entre a leitura e o compare-and-exchange é exatamente quando outra thread pode intervir, e cmpxchg detecta isso ao se recusar a armazenar um valor calculado a partir de uma leitura desatualizada.

Vale conhecer uma sutileza. cmpxchg verifica se o valor é igual ao que foi lido, não se a posição nunca foi tocada. Se outra thread mover o valor de A para B e de volta para A dentro da janela, a troca ainda assim terá sucesso, mesmo que o mundo tenha mudado por baixo.

Para um contador simples isso é inofensivo, já que uma contagem igual é uma contagem igualmente boa. Para um endereço de memória na cabeça de uma lista sem lock, não é, porque o mesmo endereço pode agora levar a outro lugar. Esse é o problema ABA.

A solução usual para esse problema é emparelhar o valor com algum "carimbo", por exemplo um contador que só cresce. Como o carimbo só avança, um carimbo correspondente prova que a posição não foi tocada no meio do caminho, e não apenas que ela parece inalterada.

Para que isso funcione em um ambiente multithread, porém, tanto o endereço de memória quanto seu carimbo precisam ser atualizados juntos. Como um endereço de memória ocupa um qword inteiro no x86-64, um cmpxchg não basta para atualizá-lo e também atualizar outro valor ao mesmo tempo.

Existe uma instrução de largura dupla chamada cmpxchg16b, semanticamente igual a cmpxchg, mas que trabalha em 16 bytes de uma vez e pode ser usada nessa situação. Ela não tem operando de origem, usando rcx:rbx como valor de substituição. Seu único operando é uma posição de memória alinhada em 16 bytes. Essa instrução também usa rdx:rax como acumulador, em vez de apenas rax.

Ordenação de Memória

Todas as operações até aqui tocaram uma única posição. Quando as threads se coordenam por meio de mais de uma posição, surge uma nova pergunta: em que ordem as escritas de uma thread se tornam visíveis para outra. As regras que respondem a essa pergunta são a ordenação de memória do processador.

O conceito de código sem branches apresentou a ideia de que um núcleo moderno não percorre as instruções uma a uma, devagar. Ele mantém muitas em andamento ao mesmo tempo e avança onde pode. Isso significa que uma escrita pode se tornar visível para os outros núcleos mais tarde do que o programa sugere, enquanto as instruções seguintes já avançaram.

O x86-64 mantém uma ordenação de memória forte entre loads e stores comuns, de modo que em cada núcleo:

1. um load nunca é reordenado depois de um load posterior;
2. um store nunca é reordenado depois de um store posterior;
3. um load nunca é reordenado depois de um store posterior.

A única reordenação possível é um store parecer se completar depois de um load posterior de um endereço diferente.

Uma instrução com o prefixo lock, ou um xchg com operando de memória, é uma barreira completa: nada parece atravessá-la em nenhuma direção. É por isso que elas bastam para garantir a ordenação completa na maioria das situações.

O mecanismo por trás da única reordenação que sobrevive é o store buffer. Para continuar avançando, um núcleo deixa cada store nesse buffer e permite que as instruções seguintes prossigam antes de o store chegar à memória que os outros núcleos conseguem ver. Uma escrita seguida de uma leitura de uma posição diferente pode, então, parecer fora de ordem: a escrita ainda pode estar no buffer enquanto a leitura posterior avança. Esse modelo, em que tudo é ordenado exceto esse intervalo entre escrita e leitura, é chamado de total store order.

Esse único intervalo basta para quebrar um handshake de escrever e depois verificar. Se duas threads escrevem cada uma sua própria flag e depois leem a da outra, as duas leituras podem voltar sem o valor definido, porque nenhum dos stores saiu do store buffer ainda. A instrução mfence fecha o intervalo ao esvaziar o store buffer: toda escrita antes dela se torna visível antes de qualquer leitura depois dela.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

Existem também duas barreiras mais estreitas:

• sfence ordena escritas entre si e importa principalmente com stores streaming non-temporais;
• lfence ordena leituras.

Para os padrões atômicos comuns acima, as instruções com o prefixo lock já carregam a ordenação completa, então uma barreira explícita só é necessária para um handshake construído com stores e loads simples, como o de cima.

Essas garantias têm nomes que vão além do x86. Uma operação tem ordenação acquire quando nenhum acesso posterior pode parecer se mover antes dela, e ordenação release quando nenhum acesso anterior pode parecer se mover depois dela. No x86, todo load é um acquire, todo store é um release, e uma instrução com o prefixo lock, ou um xchg com memória, é ambos ao mesmo tempo.

Espera ativa e pause

As instruções que definem uma flag e ao mesmo tempo retornam seu estado anterior são conhecidas como test-and-set. Elas podem servir de base para um spinlock, garantindo que um núcleo tenha acesso exclusivo a alguma parte do código.

Este é o algoritmo geral, usando a instrução xchg com uma flag binária:

1. A flag começa como 0.
2. Para adquirir o lock, um núcleo troca o valor da flag por 1.
3. Se o valor retornado for 1, isso significa que o lock está ocupado por outro núcleo. O núcleo atual então espera e tenta adquirir o lock de novo.
4. Se o valor retornado for 0, isso significa que o lock estava livre. O xchg agora o definiu como 1, e os outros núcleos vão esperar até que este núcleo o libere.
5. Quando o núcleo atual termina o trabalho, atualizar a flag com 0 libera o lock.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

A instrução pause no laço de espera não muda o que o código calcula. Ela dá uma dica ao processador de que se trata de uma espera ativa. A CPU pode então reduzir o consumo de energia na thread que espera e ceder a uma thread irmã que compartilha o mesmo núcleo. Um laço de espera sem pause continua correto, só que desperdiça recursos.

Repare que, em um test-and-set, uma instrução como xchg sempre define a flag, mesmo quando ela já estava definida. Isso significa que ela obtém acesso exclusivo à memória a cada tentativa, mesmo quando é provável que o lock ainda esteja ocupado.

Há uma variante desse algoritmo, conhecida como test-and-test-and-set, que primeiro testa (lê) a flag para verificar se ela já está definida. Ela só tenta o test-and-set (o xchg, neste caso) quando o lock parece livre:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

Quando a thread termina seu trabalho, ela pode liberar o lock com um store simples de 0 usando mov. Nada mais que um mov é necessário, porque no x86-64 loads e stores nunca são reordenados depois de um store posterior. Um store que nunca ultrapassa os acessos anteriores a ele tem ordenação release, e no x86 todo store simples carrega essa garantia.