¿Cómo puedo implementar el contador ABA con c++ 11 CAS?

multithreading c++11

Question

Estoy implementando una cola sin bloqueo basada en este algorithm , que utiliza un contador para resolver el problema ABA. Pero no sé cómo implementar este contador con c ++ 11 CAS. Por ejemplo, desde el algoritmo:

E9:    if CAS(&tail.ptr->next, next, <node, next.count+1>)

Es una operación atómica, lo que significa que si tail.ptr->next es igual a next , deje que tail.ptr->next apunte al node y simultáneamente (atómicamente) haga next.count+1 . Sin embargo, usando C ++ 11 CAS, solo puedo implementar:

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

que no puede hacer que next.count+1 ocurra simultáneamente.

Answer 1

Para modificar atómicamente dos cosas a la vez con una sola operación atómica, debe colocarlas en la memoria adyacente, por ejemplo, en una estructura de dos miembros. Entonces puede usar std::atomic<my_struct> para hacer que gcc emita lock cmpxchg16b en x86-64, por ejemplo.

No necesita asm en línea para esto, y vale la pena un poco de dolor de sintaxis de C ++ para evitarlo. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Desafortunadamente, con los compiladores actuales, debe usar una union para obtener un código eficiente para leer solo uno de los pares. La forma "obvia" de hacer una carga atómica de la estructura y luego usar solo un miembro todavía conduce a un lock cmpxchg16b para leer la estructura completa, aunque solo necesitamos un miembro. Estoy seguro de que una carga normal de 64b del puntero aún implementaría correctamente la semántica de ordenamiento de memoria adquirida en x86 (así como la atomicidad), pero los compiladores actuales no hacen esa optimización incluso para std::memory_order_relaxed , por lo que std::memory_order_relaxed ellos en él con una unión.

(Se envió el error 80835 de GCC sobre esto. TODO: lo mismo para el sonido metálico si es una idea útil).

Lista de verificación:

• Asegúrese de que su compilador esté generando un código eficiente para cargar solo un miembro en el caso de solo lectura, no un lock cmpxchg16b del par. por ejemplo, usar una unión.
• Asegúrese de que su compilador garantiza que el acceso a un miembro de un sindicato después de escribir un miembro de un sindicato diferente tiene un comportamiento bien definido en esa implementación. La tipología de unión es legal en C99 (por lo que esto debería funcionar bien con C11 stdatomic ), pero es UB en ISO C ++ 11 . Sin embargo, es legal en el dialecto GNU de C ++ (soportado por gcc, clang e ICC, entre otros).
• Asegúrese de que su objeto esté alineado con 16B o con 8B para punteros de 32 bits. Más generalmente, las alignas(2*sizeof(void*)) deberían funcionar. Las instrucciones de lock desalineadas pueden ser muy lentas en x86, especialmente si cruzan un límite de línea de caché. clang3.8 incluso lo compila en una llamada a la biblioteca si el objeto no está alineado.

• Compile con -mcx16 para compilaciones x86-64. cmpxchg16b no era compatible con las primeras CPU x86-64 (AMD K8), pero debería estar en todo después de eso. Sin -mcx16 , obtiene una llamada a la función de biblioteca (que probablemente usa un bloqueo global). El equivalente de 32 bits, cmpxchg8b , es lo suficientemente antiguo como para que los compiladores modernos asuman su soporte. (Y puede usar SSE, MMX o incluso x87 para hacer cargas / almacenes atómicos de 64b, por lo que usar una unión es algo menos importante para un buen rendimiento al leer un miembro).

• Asegúrese de que un puntero + uintptr_t objeto atómico esté libre de bloqueos. Esto está prácticamente garantizado para ABI x32 y 32 bits (objeto 8B), pero no para objetos 16B. Por ejemplo, MSVC utiliza un bloqueo para x86-64.

  gcc7 y versiones posteriores llamarán libatomic en lugar de lock cmpxchg16b , y devolverán false de atomic_is_lock_free ( por razones que incluyen que es tan lento que no es lo que los usuarios esperan que signifique is_lock_free ), pero al menos por ahora la implementación de libatomic todavía usa lock cmpxchg16b en objetivos donde esa instrucción está disponible. (Incluso puede segfault para objetos atómicos de solo lectura, por lo que realmente no es ideal).

Aquí hay un ejemplo de código con un bucle de reintento de CAS que se compila en un asm que se ve bien, y creo que está libre de UB u otro C ++ inseguro para implementaciones que permiten el castigo de tipo union. Está escrito en estilo C (funciones que no son miembros, etc.) pero sería lo mismo si escribiera funciones miembro.

Vea el código con salida asm de gcc6.3 en el explorador del compilador Godbolt . Con -m32 , usa cmpxchg8b la misma manera que el código de 64 bits usa cmpxchg16b . Con -mx32 (punteros de 32 bits en modo largo) simplemente puede usar un cmpxchg 64 bits y cargas enteras normales de 64 bits para agarrar ambos miembros en una carga atómica.

Este es C ++ 11 portátil (excepto la unión de tipo punción), sin nada específico de x86. Sin embargo, solo es eficiente en objetivos que pueden CASAR un objeto del tamaño de dos punteros. por ejemplo, compila una llamada a una función de biblioteca __atomic_compare_exchange_16 para ARM / ARM64 y MIPS64, como puede ver en Godbolt.

No se compila en MSVC, donde atomic<counted_ptr> es más grande que counted_ptr_separate , por lo que counted_ptr_separate lo static_assert . Presumiblemente, MSVC incluye un miembro de bloqueo en el objeto atómico.

#include <atomic>
#include <stdint.h>

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<node *>    ptr;
    atomic<uintptr_t> count_separate;  // var name emphasizes that accessing this way isn''t atomic with ptr
  };

  static_assert(sizeof(atomic<counted_ptr>) == sizeof(counted_ptr_separate), "atomic<counted_ptr> isn''t the same size as the separate version; union type-punning will be bogus");
  //static_assert(std::atomic<counted_ptr>{}.is_lock_free());

  union {  // anonymous union: the members are directly part of struct node
    alignas(2*sizeof(node*)) atomic<counted_ptr> 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 );
}

La salida asm de clang 4.0 -O3 -mcx16 es:

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

gcc hace algunas compras / recargas torpes, pero es básicamente la misma lógica.

follow(node*) compila a mov rax, [rdi] / ret , por lo que el acceso de solo lectura al puntero es tan barato como debería ser, gracias al truco de la unión.

Depende de escribir una unión a través de un miembro y leerlo a través de otro, para hacer lecturas eficientes de solo el puntero sin usar un lock cmpxchg16b . Se garantiza que esto funcione en GNU C ++ (e ISO C99 / C11), pero no en ISO C ++. Muchos otros compiladores de C ++ garantizan que la unión de tipos funciona, pero incluso sin eso probablemente todavía funcionaría: siempre estamos usando cargas std::atomic que deben suponer que el valor se modificó de forma asíncrona. Por lo tanto, debemos ser inmunes a los problemas de alias, en los que los valores en los registros aún se consideran vivos después de escribir el valor a través de otro puntero (o miembro de la unión). Sin embargo, el reordenamiento en tiempo de compilación de cosas que el compilador cree que son independientes podría ser un problema.

Leer atómicamente solo el puntero después de un cmpxchg atómico del puntero + contador aún debería proporcionarle semántica de adquisición / liberación en x86, pero no creo que ISO C ++ diga nada al respecto. Supongo que un amplio release-store (como parte de compare_exchange_weak se sincronizará con una carga más estrecha desde la misma dirección en la mayoría de las arquitecturas (como lo hace en x86), pero AFAIK C ++ std::atomic no garantiza nada sobre el tipo -punning

No es relevante para el puntero + contador ABA, pero podría surgir para otras aplicaciones de uso de una unión para permitir el acceso a subconjuntos de objetos atómicos más grandes: no use la unión para permitir que las tiendas atómicas solo sean el puntero o solo el contador . Al menos no si te importa la sincronización con una carga de adquisición del par. Incluso el x86 fuertemente ordenado puede reordenar una tienda estrecha con una carga más amplia que lo contenga por completo . Todo sigue siendo atómico, pero entras en un territorio extraño en lo que respecta al orden de la memoria.

En x86-64, una carga atómica de 16B requiere un lock cmpxchg16b (que es una barrera de memoria completa, evitando que una tienda estrecha anterior se vuelva globalmente visible después de ella). Pero podría tener un problema fácilmente si estuviera usando esto con punteros de 32 bits (o índices de matriz de 32 bits), ya que ambas mitades podrían cargarse con una carga normal de 64b. Y no tengo idea de qué problemas podría ver en otras arquitecturas, si necesita sincronización con otros hilos y no solo atomicidad.

Para obtener más información sobre la adquisición y el lanzamiento de std :: memory_order , consulte los excelentes artículos de Jeff Preshing .