Ponteiros de perigo e o problema ABA

Em código sem bloqueios que usa ponteiros, um valor pode ser A, mudar para B e depois voltar a A. Um CAS que compara apenas o valor não consegue saber que algo mudou nesse intervalo.

A linha de execução 1 lê o ponteiro A e se prepara para executar CAS. Enquanto isso, a linha de execução 2 exclui A, aloca um novo nó que, por acaso, reutiliza o endereço de A, e o CAS da linha de execução 1 é bem-sucedido por engano.

Uma solução é armazenar um contador junto com o ponteiro. O valor combinado muda a cada operação, tornando o ABA detectável.

As marcações exigem operações atômicas de largura dupla (por exemplo, CMPXCHG16B em x86). Elas ocupam mais espaço e podem não estar disponíveis em todas as plataformas.

A questão fundamental é: como excluir um nó que outras linhas de execução ainda podem estar acessando? O código sem bloqueios não pode usar um delete simples.

Cada linha de execução publica o ponteiro que está acessando no momento em uma lista global de riscos. Antes de liberar a memória, uma linha de execução examina a lista de riscos — se alguém estiver usando o ponteiro, adie a exclusão.

Para cada acesso:

1. Leia o ponteiro atomicamente
2. Publique-o como um risco
3. Leia-o novamente para confirmar que não mudou (evite uma condição de corrida)
4. Use-o
5. Limpe o risco

Quando um nó não puder mais ser alcançado, adicione-o a uma lista de nós aposentados por linha de execução. Examine periodicamente todos os riscos; os nós que não estiverem presentes em nenhum risco poderão ser excluídos com segurança.

Uma alternativa é dividir o tempo em épocas. Um nó pode ser excluído quando todas as linhas de execução tiverem avançado além da época em que ele foi aposentado. Essa abordagem é usada no Crossbeam (Rust) e em estruturas de dados concorrentes.

Incremente um contador por nó durante a leitura e decremente-o após o uso. É simples, mas mais lento que os ponteiros de risco — cada operação adiciona incrementos e decrementos atômicos.

O ABA só é um problema quando há uma "lista livre" ou quando os endereços de memória são reutilizados. Com liberação segura (ponteiros de risco ou épocas), o problema geralmente desaparece.

Estruturas de dados sem bloqueios são verdadeiros campos minados. Use implementações comprovadas do Folly, Boost ou Crossbeam (Rust). Crie sua própria implementação apenas para fins educacionais ou para caminhos específicos e críticos para o desempenho, depois de fazer medições cuidadosas.

ThreadSanitizer detecta condições de corrida nos dados, mas não todos os problemas de correção do código sem bloqueios. Ferramentas de verificação formal (CDSChecker, Relacy) exploram sistematicamente as intercalações.

A que o problema ABA se refere na programação sem bloqueios?

O problema ABA afeta código sem bloqueios que reutiliza endereços de memória. Ponteiros marcados, ponteiros de risco e liberação baseada em épocas são as soluções tradicionais. Garantir a correção de código sem bloqueios é difícil — prefira bibliotecas comprovadas a implementações feitas manualmente.