Noite de estreia

Operações atômicas

Uma única instrução pode parecer uma ação indivisível e não ser 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 divide essa única instrução em três etapas menores, chamadas de 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 leitura-modificação-escrita (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 todo o seu efeito antes da próxima. Essa janela é, portanto, invisível, e o add se comporta como uma unidade única.

No entanto, as CPUs modernas raramente têm um único núcleo, e os aplicativos costumam rodar em vários núcleos ao mesmo tempo, sem nenhuma ordenação entre eles. Com vários núcleos rodando no exato mesmo instante, outro núcleo pode ler ou escrever o counter dentro dessa janela, depois do load deste núcleo e antes do seu store. Duas threads carregam o mesmo valor antigo, cada uma soma cinco e cada uma armazena seu resultado. Duas somas aconteceram, mas o valor avançou apenas cinco. Uma atualização foi perdida em silêncio.

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

Nem todo valor fica exposto desse jeito. Cada thread tem seus próprios registradores e sua própria pilha, então um valor guardado 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 o 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 unidade única 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 inteira, 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 valer o valor anterior do operando de origem, e o operando de origem passa a valer o valor anterior do operando de destino. Conceitualmente, dá para pensar nela como duas instruções mov acontecendo ao mesmo tempo.

Como de costume, ela 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, a xchg é sempre atômica.

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 uma única etapa indivisível. Isso significa que o núcleo mantém a memória com exclusividade durante todo o processo, então nenhum outro núcleo consegue ler ou escrever nesse endereço no meio do caminho.

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

O lock só funciona quando o destino é a memória, e apenas em instruções que fazem leitura-modificação-escrita 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.

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 diferente.

A instrução xadd (x de exchange, troca) 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.

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.

Comparação e troca

O xadd soma e o xchg sobrescreve, mas nenhum dos dois consegue fazer o novo valor depender do atual e aplicá-lo apenas se nada tiver mudado por baixo. É essa atualização condicional que o cmpxchg, compare-and-exchange (comparação e troca), oferece, e ela é a mais geral dessas primitivas.

cmpxchg dest, src usa o 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.

Repare que o dest só é atualizado quando ele é igual ao valor esperado, previamente carregado no rax. Essa igualdade garante que o 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 a peça fundamental 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 retentativa é o coração das atualizações lock-free. A janela entre a leitura e a comparação e troca é exatamente quando outra thread pode intervir, e o cmpxchg detecta isso ao se recusar a armazenar um valor calculado a partir de uma leitura desatualizada.

Ordenação de memória

Toda operação até aqui mexeu em um único endereço. Quando as threads se coordenam por meio de mais de um endereç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 ramificações apresentou a ideia de que um núcleo moderno não avança pelas instruções uma de cada vez. Ele mantém muitas em execução ao mesmo tempo e segue adiante sempre que pode. Isso significa que uma escrita pode se tornar visível para os outros núcleos mais tarde do que o programa sugere, enquanto instruções posteriores a ela já seguiram adiante.

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

1. uma leitura nunca é reordenada para depois de uma leitura posterior;
2. uma escrita nunca é reordenada para depois de uma escrita posterior;
3. uma leitura nunca é reordenada para depois de uma escrita posterior.

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

Uma instrução com o prefixo lock, ou um xchg com um 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.

Espera ativa e pause

As instruções que definem uma flag e também 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 em 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 outro núcleo está com o lock. 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. A 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 seu 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 avisa o 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 espaço para uma thread irmã que compartilha o mesmo núcleo. Um laço de espera ativa sem pause continua correto, apenas desperdiça recursos.

Quando a thread termina seu trabalho, ela pode liberar o lock com uma escrita simples de 0 usando mov. Nada além de um mov é necessário, porque no x86-64 leituras e escritas nunca são reordenadas para depois de uma escrita posterior. Diz-se que uma escrita que nunca ultrapassa os acessos anteriores tem ordenação de liberação, e no x86 toda escrita simples carrega essa propriedade.