Como posso implementar o contador ABA com o c ++ 11 CAS?

Estou implementando uma fila livre de bloqueio com base nesse algoritmo , que usa um contador para resolver o problema do ABA. Mas eu não sei como implementar esse contador com o c ++ 11 CAS. Por exemplo, do algoritmo:

E9: if CAS(&tail.ptr->next, next, ) 

É uma operação atômica, significando que se tail.ptr->next for igual a next , deixe tail.ptr->next point to node e simultaneamente ( next.count+1 ) faça next.count+1 . No entanto, usando o C ++ 11 CAS, só posso implementar:

 std::atomic_compare_exchange_weak(&tail.ptr->next, next, node); 

que não pode fazer next.count+1 acontecer simultaneamente.

   

Para modificar atomicamente duas coisas ao mesmo tempo com uma única operação atômica, você precisa colocá-las na memory adjacente, por exemplo, em uma estrutura de dois membros. Então você pode usar o std::atomic para fazer com que o gcc emita o lock cmpxchg16b no x86-64, por exemplo.

Você não precisa de um inline asm para isso, e vale a pena um pouco de dor na syntax C ++ para evitá-lo. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Infelizmente, com os compiladores atuais, você precisa usar uma union para obter um código eficiente para a leitura de apenas um dos pares. A maneira “óbvia” de fazer uma carga atômica da estrutura e, em seguida, usar apenas um membro ainda leva a um lock cmpxchg16b para ler toda a estrutura, embora seja necessário apenas um membro. Estou confiante de que uma carga normal de 64b do ponteiro ainda implementaria corretamente a semântica de ordenação de memory no x86 (assim como a atomicidade), mas compiladores atuais não fazem essa otimização mesmo para std::memory_order_relaxed , então nós std::memory_order_relaxed . -los com um sindicato.

( Enviou o bug do GCC 80835 sobre isso. TODO: mesmo para clang se esta é uma idéia útil.)


Lista de controle:

  • Certifique-se de que seu compilador está gerando código eficiente para carregar apenas um membro no caso somente leitura, não um lock cmpxchg16b do par. por exemplo, usando uma união.
  • Certifique-se de que seu compilador garanta que acessar um membro de um sindicato depois de escrever um membro de união diferente tenha um comportamento bem definido nessa implementação. A união de tipos é legal em C99 (portanto, isso deve funcionar bem com o C11 stdatomic ), mas é o UB no ISO C ++ 11 . No entanto, é legal no dialeto GNU do C ++ (suportado pelo gcc, clang e ICC, entre outros).
  • Certifique-se de que seu object esteja alinhado em 16B ou alinhado em 8B para pointers de 32 bits. Mais geralmente, alignas(2*sizeof(void*)) deve funcionar. Instruções de lock desalinhadas podem ser muito lentas no x86, especialmente se elas cruzarem um limite de linha de cache. clang3.8 até compila para uma chamada de biblioteca se o object não estiver alinhado.
  • Compile com -mcx16 para construções x86-64. cmpxchg16b não era suportado pelos primeiros processadores x86-64 (AMD K8), mas deveria estar em tudo depois disso. Sem -mcx16 , você obtém uma chamada de function de biblioteca (que provavelmente usa um bloqueio global). O equivalente de 32 bits, cmpxchg8b , é antigo o suficiente para que os compiladores modernos assumam seu suporte. (E pode usar SSE, MMX ou até x87 para fazer cargas / armazenamentos atômicos de 64b, portanto, usar uma união é um pouco menos importante para um bom desempenho ao ler um membro).

  • Certifique-se de que um ponteiro + uintptr_t object atômico esteja livre de bloqueio. Isso é praticamente garantido para ABIs de 32 e 32 bits (object 8B), mas não para objects de 16B. Por exemplo, o MSVC usa um bloqueio para x86-64.

    O gcc7 e mais tarde chamarão libatomic em vez de inlining lock cmpxchg16b , e retornarão false de atomic_is_lock_free ( por razões incluindo que é tão lento não é o que os usuários esperam que is_lock_free signifique ), mas pelo menos por enquanto a implementação libatomic ainda usa lock cmpxchg16b em targets onde essa instrução está disponível. (Ele pode até se separar para objects atômicos de somente leitura, então não é o ideal.)


Aqui está um exemplo de código com um loop de repetição de CAS que compila para um aspecto que parece certo, e eu acho que é livre de UB ou outro C ++ inseguro para implementações que permitem punir tipo de união. Está escrito em estilo C (funções não membro, etc.), mas seria o mesmo se você escrevesse funções de membro.

Veja o código com saída asm do gcc6.3 no explorador do compilador Godbolt . Com o -m32 , ele usa o cmpxchg8b da mesma forma que o código de 64 bits usa o cmpxchg16b . Com -mx32 (pointers de 32 bits em modo longo) pode simplesmente usar um cmpxchg 64 bits e cargas inteiras normais de 64 bits para capturar os dois membros em uma carga atômica.

Este é o C ++ 11 portátil (exceto o puncionamento de tipo de união), sem nada específico ao x86. No entanto, é apenas eficiente em alvos que podem casar um object do tamanho de dois pointers. Por exemplo, ele compila uma chamada para uma function de biblioteca __atomic_compare_exchange_16 para ARM / ARM64 e MIPS64, como você pode ver no Godbolt.

Ele não compila no MSVC, onde atomic é maior que counted_ptr_separate , então o static_assert pega. Presumivelmente, o MSVC inclui um membro de bloqueio no object atômico.

 #include  #include  using namespace std; struct node { // This alignas is essential for clang to use cmpxchg16b instead of a function call // Apparently just having it on the union member isn't enough. struct alignas(2*sizeof(node*)) counted_ptr { node * ptr; uintptr_t count; // use pointer-sized integers to avoid padding }; // hack to allow reading just the pointer without lock-cmpxchg16b, // but still without any C++ data race struct counted_ptr_separate { atomic ptr; atomic count_separate; // var name emphasizes that accessing this way isn't atomic with ptr }; static_assert(sizeof(atomic) == sizeof(counted_ptr_separate), "atomic isn't the same size as the separate version; union type-punning will be bogus"); //static_assert(std::atomic{}.is_lock_free()); union { // anonymous union: the members are directly part of struct node alignas(2*sizeof(node*)) atomic next_and_count; counted_ptr_separate next; }; // TODO: write member functions to read next.ptr or read/write next_and_count int data[4]; }; // make sure read-only access is efficient. node *follow(node *p) { // good asm, just a mov load return p->next.ptr.load(memory_order_acquire); } node *follow_nounion(node *p) { // really bad asm, using cmpxchg16b to load the whole thing return p->next_and_count.load(memory_order_acquire).ptr; } void update_next(node &target, node *desired) { // read the old value efficiently to avoid overhead for the no-contention case // tearing (or stale data from a relaxed load) will just lead to a retry node::counted_ptr expected = { target.next.ptr.load(memory_order_relaxed), target.next.count_separate.load(memory_order_relaxed) }; bool success; do { node::counted_ptr newval = { desired, expected.count + 1 }; // x86-64: compiles to cmpxchg16b success = target.next_and_count.compare_exchange_weak( expected, newval, memory_order_acq_rel); // updates exected on failure } while( !success ); } 

A saída do ASM do clang 4.0- -O3 -mcx16-O3 -mcx16 é:

 update_next(node&, node*): push rbx # cmpxchg16b uses rbx implicitly so it has to be saved/restored mov rbx, rsi mov rax, qword ptr [rdi] # load the pointer mov rdx, qword ptr [rdi + 8] # load the counter .LBB2_1: # =>This Inner Loop Header: Depth=1 lea rcx, [rdx + 1] lock cmpxchg16b xmmword ptr [rdi] jne .LBB2_1 pop rbx ret 

O gcc faz alguns clunky store / reloads, mas é basicamente a mesma lógica.

follow(node*) compila para mov rax, [rdi] / ret , então o access somente leitura ao ponteiro é tão barato quanto deveria, graças ao hack da união.


Depende de escrever uma união através de um membro e lê-lo através de outro, para fazer leituras eficientes de apenas o ponteiro sem usar um lock cmpxchg16b . Isso é garantido para trabalhar no GNU C ++ (e ISO C99 / C11), mas não no ISO C ++. Muitos outros compiladores de C ++ garantem que o puncionamento de tipo de união funciona, mas mesmo sem isso provavelmente ainda funcionaria: Estamos sempre usando cargas std::atomic que devem assumir que o valor foi modificado de forma assíncrona. Portanto, devemos estar imunes a problemas do tipo aliasing, nos quais os valores nos registradores ainda são considerados ativos depois de gravar o valor por meio de outro ponteiro (ou membro do sindicato). O reordenamento em tempo de compilation de coisas que o compilador considera independentes pode ser um problema.

Atomicamente lendo apenas o ponteiro após um cmpxchg atômico do ponteiro + contador ainda deve dar-lhe adquirir / liberar semântica no x86, mas eu não acho que o ISO C + + diz nada sobre isso. Eu diria que um amplo release-store (como parte do compare_exchange_weak será sincronizado com uma carga mais restrita do mesmo endereço na maioria das arquiteturas (como acontece no x86), mas o AFAIK C ++ std::atomic não garante nada sobre o tipo -assistindo.

Não relevante para ponteiro + contador ABA, mas poderia surgir para outras aplicações de uso de uma união para permitir o access a subconjuntos de objects atômicos maiores: Não use a união para permitir armazenamentos atômicos apenas para o ponteiro ou apenas para o contador . Pelo menos não se você se preocupa com a synchronization com uma carga de aquisição do par. Mesmo o x86 com pedidos intensos pode reordenar um armazenamento restrito com uma carga mais ampla que o contenha totalmente . Tudo ainda é atômico, mas você entra em território estranho no que diz respeito à ordenação de memory.

Em x86-64, uma carga atômica de 16B requer um lock cmpxchg16b (que é uma barreira de memory completa, impedindo que um armazenamento restrito anterior se torne globalmente visível após ele). Mas você poderia facilmente ter um problema se você estivesse usando isso com pointers de 32 bits (ou índices de array de 32 bits), já que ambas as metades poderiam ser carregadas com uma carga normal de 64b. E eu não tenho ideia de quais problemas você poderia ver em outras arquiteturas, se você precisa de synchronization com outros threads e não apenas atomicidade.


Para aprender mais sobre std :: memory_order, adquira e libere , veja os excelentes artigos de Jeff Preshing .