Noite de estreia

Atómicos

Uma única instrução pode parecer uma ação indivisível quando não o é de todo. Vejamos o caso de somar cinco a um valor em 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 carregamento) e a escrita (ou armazenamento) são eventos separados, pelo que existe uma janela de tempo entre eles. Normalmente não damos por isso porque, num único núcleo, cada instrução tem garantia de produzir o seu efeito por completo antes da seguinte. Essa janela é, portanto, invisível e o add comporta-se como uma única unidade.

No entanto, os CPUs modernos raramente têm um único núcleo, e as aplicações correm muitas vezes em vários núcleos ao mesmo tempo, sem sequenciação entre eles. Com vários núcleos a correr no mesmo instante, outro núcleo pode ler ou escrever o counter dentro dessa janela, depois do carregamento deste núcleo e antes do seu armazenamento. Duas threads carregam cada uma o mesmo valor antigo, cada uma soma cinco e cada uma armazena o seu resultado. Ocorreram duas adições, mas o valor só avançou cinco. Uma atualização foi silenciosamente perdida.

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

Nem todos os valores estão expostos desta forma. Cada thread tem os seus próprios registos e a sua própria pilha, pelo que 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. 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 passa a ser igual ao valor anterior no operando de origem, enquanto o operando de origem passa a ser igual ao valor anterior no 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, o xchg é sempre atómico.

O prefixo lock

A forma mais comum de tornar uma instrução atómica em x86-64 é acrescentar-lhe o prefixo lock. 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 nessa 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 abaixo.

Troca e Adição

Um lock add simples 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 ao mesmo tempo que 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. Executada por muitas threads sobre o 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 também são devolvidos, um a cada chamador.

Comparação e Troca

O xadd soma e o xchg substitui, mas nenhum deles consegue fazer com que o novo valor dependa do atual e o aplique apenas se nada tiver mudado por baixo. Essa atualização condicional é o que o cmpxchg, comparação e troca, proporciona, e é a mais geral destas primitivas.

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.

Repara 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, pelo que nunca se aplica uma atualização baseada numa leitura obsoleta. Isso faz do cmpxchg a peça base 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 coração das atualizações sem bloqueio. A janela entre a leitura e a comparação e troca é exatamente quando outra thread pode intervir, e o cmpxchg deteta isso ao recusar-se a armazenar um valor calculado a partir de uma leitura obsoleta.

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 pergunta: por que ordem se tornam visíveis para outra thread as escritas de uma thread. As regras que respondem a esta pergunta 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 a passo vagaroso, uma a uma. Mantém muitas em curso ao mesmo tempo e avança à frente sempre que pode. Isto significa que uma escrita pode tornar-se visível para os outros núcleos mais tarde do que o programa sugere, enquanto instruções posteriores já avançaram.

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

1. um carregamento nunca é reordenado depois de um carregamento posterior;
2. um armazenamento nunca é reordenado depois de um armazenamento posterior;
3. um carregamento nunca é reordenado depois de um armazenamento posterior.

A única reordenação possível é um armazenamento parecer concluir-se depois de um carregamento 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 mover-se através dela em qualquer direção. É por isso que são suficientes para garantir a ordenação completa na maioria das situações.

Espera ativa e pause

As instruções que definem um sinalizador e devolvem ao mesmo tempo o seu estado anterior são conhecidas como test-and-set. Podem servir de base a 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 sinalizador binário:

1. O sinalizador começa em 0.
2. Para adquirir o bloqueio, um núcleo troca o valor no sinalizador 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 novamente.
4. Se o valor devolvido for 0, isso significa que o bloqueio estava livre. O xchg já o colocou em 1, e os outros núcleos esperarão até este núcleo o libertar.
5. Quando o núcleo atual termina o trabalho, atualizar o sinalizador 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 altera o 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 em espera e ceder a uma thread irmã que partilhe o mesmo núcleo. Um ciclo de espera sem pause continua a ser correto, apenas desperdiça recursos.

Quando a thread termina o seu trabalho, pode libertar o bloqueio com um simples armazenamento de 0 através de mov. Não é preciso mais do que um mov, porque no x86-64 os carregamentos e armazenamentos nunca são reordenados depois de um armazenamento posterior. Um armazenamento que nunca ultrapassa os acessos que o antecedem diz-se ter ordenação de libertação, e no x86 todos os armazenamentos comuns a têm.