Operações atómicas em

Sobre Operações atómicas

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

add qword [rel counter], 5

Por baixo, o processador não tem forma de somar diretamente à memória. Divide esta única instrução em três passos mais pequenos, chamados micro-operações:

1. ler o valor atual da memória;
2. modificar esse valor num registo, somando-lhe cinco;
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

Este é um padrão comum chamado leitura-modificação-escrita (RMW).

Repara que a leitura (ou load) e a escrita (ou store) são eventos separados, pelo que há uma janela de tempo entre eles. Normalmente não reparamos nisso porque, num único núcleo, é garantido que cada instrução produz o seu efeito na totalidade antes da seguinte. Essa janela é, por isso, invisível, e o add comporta-se como uma única unidade.

Contudo, os processadores modernos raramente têm um único núcleo, e as aplicações correm muitas vezes em vários núcleos ao mesmo tempo, sem qualquer sequenciação entre eles. Com vários núcleos a correr no mesmo instante, outro núcleo pode ler ou escrever counter dentro da janela, depois do load deste núcleo e antes do seu store. Duas threads carregam cada uma o mesmo valor antigo, somam-lhe cada uma cinco e guardam cada uma o seu resultado. Ocorreram duas adições, mas o valor só avançou cinco. Uma atualização perdeu-se em silêncio.

Isto é uma corrida de dados, e é um problema comum em código com várias threads.

Nem todos os valores ficam expostos desta forma. Cada thread tem os seus próprios registos e a sua própria pilha, por isso um valor guardado num registo, ou uma variável local na pilha de uma thread, é exclusivo dessa thread e não pode sofrer uma corrida. Só a memória que as threads partilham, como o counter acima, precisa de proteção.

O x86-64 oferece um conjunto de instruções para resolver este problema, tornando uma instrução indivisível. Esta comporta-se 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 coesa, que nenhum outro núcleo consegue dividir, chama-se atómica.

Troca atómica

A instrução xchg troca dois operandos. O operando de destino fica igual ao valor anterior do operando de origem, e o operando de origem fica igual ao valor anterior do operando de destino. Conceptualmente, pode pensar-se nela como duas instruções mov a acontecer ao mesmo tempo.

Como habitualmente, pode usar-se com dois operandos de registo ou com um operando de memória e um operando de registo:

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 processador bloqueia a posição durante esse período, o mesmo mecanismo que o prefixo lock usa noutras instruções, descrito a seguir.

O prefixo lock

A forma mais comum de tornar uma instrução atómica em x86-64 é acrescentar o prefixo lock. Este funde a leitura, a modificação e a escrita num único passo indivisível. Isto significa que o núcleo detém a memória em exclusivo durante todo o processo, pelo que nenhum outro núcleo pode ler ou escrever essa posição pelo meio.

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

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

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

Operações atómicas sobre bits

De entre as instruções bloqueáveis, os testes de bits combinam naturalmente com o spinlock no fim deste documento. Cada uma de bts, btr e btc copia um bit escolhido para o flag de carry e depois define-o, limpa-o ou inverte-o. Com o prefixo lock, isso torna-se uma leitura-modificação-escrita de um único bit: o bit é alterado atomicamente, e o CF indica 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

Um set que encontra o bit já definido significa que outra thread o reclamou primeiro. Esta é uma versão de um único bit do ato de reclamar um flag que o xchg faz para uma palavra inteira.

Troca e soma

Um simples lock add atualiza a memória mas deita 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) devolve o valor anterior enquanto soma. Escreve a soma no destino e deixa o valor original do destino no registo 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, isto é um fetch-and-add atómico. Executado por muitas threads no mesmo contador, cada chamada devolve um valor antigo diferente.

Tal como com o lock add, o contador termina no número exato de chamadas. No entanto, ao contrário do lock add, todos os valores intermédios são também devolvidos, um a cada invocador.

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

Comparar e trocar

O xadd soma e o xchg sobrescreve, mas nenhum deles consegue fazer o novo valor depender do atual e aplicá-lo só se nada tiver mudado por baixo. É essa atualização condicional que o cmpxchg, comparar-e-trocar, proporciona, e é o mais geral destes primitivos.

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

• Se dest == rax, dest = src e ZF = 1.
• Se dest != rax, 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.

Repara que dest só é atualizado quando é igual ao valor esperado, previamente carregado para rax. Esta igualdade garante que dest ainda contém o valor a partir do qual o novo foi calculado, pelo que uma atualização baseada numa 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

Este ciclo de repetição é o cerne das atualizações sem bloqueios. A janela entre a leitura e o comparar-e-trocar é exatamente o momento em que outra thread pode intervir, e o cmpxchg deteta isso ao recusar guardar um valor calculado a partir de uma leitura desatualizada.

Há uma subtileza que vale a pena conhecer. O cmpxchg verifica que o valor é igual ao que foi lido, e não que 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 tem sucesso, mesmo que o mundo tenha mudado por baixo.

Para um simples contador, isso é inofensivo, pois uma contagem igual é uma contagem igualmente boa. Para um endereço de memória à cabeça de uma lista sem bloqueios, já não é, porque o mesmo endereço pode agora dar para outro sítio. Este é o problema ABA.

A solução habitual para este problema emparelha o valor com uma certa "marca", por exemplo um contador que só cresce. Como a marca só avança, uma marca correspondente prova que a posição não foi tocada pelo meio, e não apenas que parece inalterada.

Para isto funcionar num ambiente com várias threads, no entanto, tanto o endereço de memória como a sua marca têm de ser atualizados em conjunto. Como um endereço de memória é um quadword completo em x86-64, um cmpxchg não basta para o atualizar a par de outro valor ao mesmo tempo.

Há uma instrução de largura dupla chamada cmpxchg16b, semanticamente igual ao cmpxchg mas que opera sobre 16 bytes de uma só vez e pode ser usada nessa situação. Não tem operando de origem; usa rcx:rbx como valor de substituição. O seu único operando é uma posição de memória alinhada a 16 bytes. Esta instrução usa também rdx:rax como acumulador, em vez de apenas rax.

Ordenação de memória

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

O conceito de código sem ramificações introduziu a ideia de que um núcleo moderno não percorre as instruções uma a uma. Mantém muitas em voo ao mesmo tempo e avança onde pode. Isto significa que uma escrita pode tornar-se 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 normais, 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 concluir-se depois de um load posterior de um endereço diferente.

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

O mecanismo por trás da única reordenação que sobrevive é o buffer de escrita. Para continuar a avançar, um núcleo estaciona cada store nesse buffer e deixa as instruções seguintes prosseguirem 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, por isso, parecer fora de ordem: a escrita pode ainda estar no buffer enquanto a leitura posterior avança. Este modelo, em que tudo está ordenado exceto essa lacuna de escrita-seguida-de-leitura, chama-se total store order.

Essa única lacuna é suficiente para quebrar um aperto de mão em que se escreve e depois se verifica. Se duas threads escreverem cada uma o seu próprio flag e depois lerem o da outra, ambas as leituras podem voltar por definir, porque nenhum dos stores saiu ainda do seu buffer de escrita. A instrução mfence fecha a lacuna ao esvaziar o buffer de escrita: todas as escritas anteriores tornam-se visíveis antes de qualquer leitura posterior.

    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:

• a sfence ordena as escritas entre si e é sobretudo relevante com os stores não temporais, de streaming;
• a lfence ordena as leituras.

Para os padrões atómicos normais acima, as instruções com o prefixo lock já trazem a ordenação completa, pelo que só é precisa uma barreira explícita para um aperto de mão construído com stores e loads normais, como o de cima.

Estas garantias têm nomes que vão além do x86. Uma operação tem ordenação acquire quando nenhum acesso posterior pode parecer mover-se para antes dela, e ordenação release quando nenhum acesso anterior pode parecer mover-se para depois dela. No x86, todos os loads são acquire, todos os stores são release, e uma instrução com o prefixo lock, ou uma xchg com memória, é ambas ao mesmo tempo.

Espera ativa e pause

As instruções que definem um flag e devolvem ao mesmo tempo o seu estado anterior são conhecidas como test-and-set. Podem ser usadas como base de um spinlock, garantindo que um núcleo tem acesso exclusivo a uma parte do código.

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

1. O flag começa em 0.
2. Para adquirir o bloqueio, um núcleo troca o valor do flag por 1.
3. Se o valor devolvido for 1, isso significa que o bloqueio está detido por outro núcleo. O núcleo atual espera então e tenta adquirir o bloqueio outra vez.
4. Se o valor devolvido for 0, isso significa que o bloqueio estava livre. A xchg definiu-o agora como 1, e os outros núcleos vão esperar até este núcleo o libertar.
5. Quando o núcleo atual termina o trabalho, atualizar o flag com 0 liberta o bloqueio.

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 ciclo de espera não muda aquilo que o código calcula. Dá uma indicação ao processador de que se trata de uma espera ativa. A CPU pode então reduzir o consumo de energia na thread à espera e ceder a uma thread irmã que partilha o mesmo núcleo. Um ciclo de espera sem pause continua correto, só que desperdiça recursos.

Repara que, num test-and-set, uma instrução como a xchg define sempre o flag, mesmo quando este já estava definido. Isto significa que obtém acesso exclusivo à memória em cada tentativa, mesmo quando é provável que o bloqueio ainda esteja detido.

Existe uma variante deste algoritmo, conhecida como test-and-test-and-set, que primeiro testa (lê) o flag para verificar se já está definido. Só depois tenta o test-and-set (a xchg, neste caso) quando o bloqueio 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

Assim que a thread termina o seu trabalho, pode libertar o bloqueio com um simples store de 0 usando mov. Não é preciso mais do que um mov, porque em x86-64 os loads e os stores nunca são reordenados depois de um store posterior. Diz-se que um store que nunca ultrapassa os acessos anteriores tem ordenação release, e no x86 todos os stores normais a têm.