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

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

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

Desafortunadamente, con los compiladores actuales, es necesario utilizar a unionpara obtener un código eficiente para leer solo uno del par. La forma "obvia" de hacer una carga atómica de la estructura y luego usar solo un miembro todavía lleva a lock cmpxchg16bleer toda la estructura aunque solo necesitemos un miembro. (Mucho más lento y ensucia la línea de caché, por lo que los lectores compiten con otros lectores). Estoy seguro de que una carga normal de 64b del puntero aún implementaría correctamente la semántica de ordenación de memoria en x86 (así como la atomicidad), pero los compiladores actuales no hacen esa optimización ni siquiera para std::memory_order_relaxed, por lo que los engañamos con una union.

(Envió el error 80835 de GCC sobre esto. TODO: lo mismo para clang si es una idea útil).

Lista de Verificación:

• Asegúrese de que su compilador esté generando código eficiente para cargar solo un miembro en el caso de solo lectura, no uno lock cmpxchg16bdel par. por ejemplo, utilizando una unión.

• Asegúrese de que su compilador garantice que acceder a un miembro de una unión después de escribir un miembro de unión diferente tenga un comportamiento bien definido en esa implementación. El juego de palabras tipo unión es legal en C99 (por lo que debería funcionar bien con C11 stdatomic), pero es UB en ISO C++11 . Sin embargo, es legal en el dialecto GNU de C++ (compatible con gcc, clang e ICC, entre otros).

• Asegúrese de que su objeto esté alineado con 16B o con 8B para punteros de 32 bits. En términos más generales, alignas(2*sizeof(void*))debería funcionar. Las instrucciones ed desalineadas lockpueden ser muy lentas en x86, especialmente si cruzan el límite de una 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. cmpxchg16bno era compatible con las primeras CPU x86-64 (AMD K8), pero debería estar en todo después de eso. Sin -mcx16, obtienes una llamada a una 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 realizar cargas/almacenamiento atómico 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 objeto atómico pointer+uintptr_t no esté bloqueado. 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 posteriores llamarán a libatomic en lugar de inlining lock cmpxchg16by devolverán false from atomic_is_lock_free( por razones que incluyen que es tan lento que no es lo que los usuarios esperan is_lock_freeque signifique ), pero al menos por ahora la implementación de libatomic todavía se usa lock cmpxchg16ben objetivos donde esa instrucción está disponible. (Incluso puede segmentar para objetos atómicos de solo lectura, por lo que en realidad no es ideal. Más importante aún, los lectores compiten con otros lectores por el acceso exclusivo a la línea de caché. Es por eso que nos vamos a tomar tantas molestias para evitarlo lock cmpxchg16ben el lado de lectura. aquí cuando solo queremos una mitad de 8 bytes).

Aquí hay un ejemplo de código con un bucle de reintento CAS que se compila en un conjunto que parece correcto, y creo que está libre de UB u otro C++ inseguro para implementaciones que permiten juegos de palabras de tipo unión. 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, utiliza cmpxchg8bla misma forma que utiliza el código de 64 bits cmpxchg16b. Con -mx32(punteros de 32 bits en modo largo), simplemente puede usar cmpxchgcargas enteras de 64 bits y normales de 64 bits para capturar ambos miembros en una carga atómica.

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

No se compila en MSVC, donde atomic<counted_ptr>es mayor que counted_ptr_separate, por lo que static_assertlo detecta. 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 );
}

El resultado del ensamblaje de clang 4.0 -O3 -mcx16es:

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 realiza algunas recargas/almacenamiento torpes, pero es básicamente la misma lógica.

follow(node*)compila en 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 unión.

Depende de escribir una unión a través de un miembro y leerla a través de otro, para realizar lecturas eficientes solo del puntero sin usar un archivolock cmpxchg16b . Se garantiza que esto funcionará en GNU C++ (e ISO C99/C11), pero no en ISO C++. Muchos otros compiladores de C++ garantizan que el juego de palabras con tipos de unión funciona, pero incluso sin eso probablemente seguiría funcionando: siempre usamos std::atomiccargas que deben asumir que el valor se modificó de forma asincrónica. Por lo tanto, deberíamos ser inmunes a problemas similares a los de alias en los que los valores en los registros todavía se consideran activos después de escribir el valor a través de otro puntero (o miembro de la unión). Sin embargo, reordenar en tiempo de compilación las cosas que el compilador considera independientes podría ser un problema.

La lectura atómica solo del puntero después de un cmpxchg atómico del puntero+contador debería proporcionarle la semántica de adquisición/liberación en x86, pero no creo que ISO C++ diga nada al respecto. Supongo que una amplia tienda de lanzamientos (como parte de la compare_exchange_weaksincronización 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::atomicno garantiza nada sobre los juegos de palabras.

No es relevante para 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 almacenes atómicos solo para el puntero o solo el contador . Al menos no si le importa la sincronización con una carga de adquisición del par. Incluso un x86 fuertemente ordenado puede reordenar un almacén estrecho con una carga más amplia que lo contenga por completo . Todo sigue siendo atómico, pero te adentras en un territorio extraño en lo que respecta al ordenamiento de la memoria.

En x86-64, una carga atómica de 16B requiere lock cmpxchg16b(que es una barrera de memoria completa, que evita que un almacén estrecho anterior se vuelva globalmente visible después de él). Pero fácilmente podría tener un problema 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 subprocesos 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 .

Aug 17 '2016 08:08 Peter Cordes