Recuento de referencias sin bloqueo y punteros inteligentes C++

En general, las implementaciones más conocidas de clases de ptr inteligentes de recuento de referencias en C++, incluido el estándar std::shared_ptr, utilice el recuento de referencias atómicas, pero no proporcione acceso atómico a la misma instancia de ptr inteligente. En otras palabras, múltiples subprocesos pueden operar de forma segura en distintos shared_ptr instancias que apuntan al mismo objeto compartido, pero múltiples subprocesos no poder instancias de lectura/escritura seguras del mismo shared_ptr instancia sin proporcionar algún tipo de sincronización, como un mutex o lo que sea.

Una versión atómica de un shared_ptr llamó “atomic_shared_ptr” ha sido propuestoy preliminar implementaciones ya existe. Presumiblemente, atomic_shared_ptr podría implementarse fácilmente con un bloqueo de giro o mutex, pero también es posible una implementación sin bloqueo.

Después de estudiar algunas de estas implementaciones, una cosa es obvia: implementar un sistema sin bloqueo std::shared_ptr es muy difícil, y parece requerir tantos compare_and_exchange operaciones como para hacerme cuestionar si un simple bloqueo de giro lograría un mejor rendimiento.

La razón principal por la que es tan difícil implementar un puntero de conteo de referencia sin bloqueo es por la carrera que siempre existe entre lectura el bloque de control compartido (o el propio objeto compartido, si estamos hablando de un puntero compartido intrusivo) y modificando el recuento de referencias.

En otras palabras, ni siquiera puede leer con seguridad el recuento de referencias porque nunca se sabe cuándo algún otro subproceso ha desasignado la memoria donde vive el recuento de referencias.

Entonces, en general, se emplean varias estrategias complejas para crear versiones sin bloqueo. los implementación aquí parece que usa una estrategia de conteo de doble referencia, donde hay referencias “locales” que cuentan la cantidad de subprocesos que acceden simultáneamente al shared_ptr instancia, y luego referencias “compartidas” o “globales” que cuentan el número de instancias shared_ptr que apuntan al objeto compartido.

Dada toda esta complejidad, me sorprendió mucho encontrar un artículo del Dr. Dobbs, de 2004 nada menos (mucho antes de C ++ 11 atomics) que parece resolver con indiferencia todo este problema:

http://www.drdobbs.com/atomic-reference-counting-pointers/184401888

Parece que el autor afirma ser capaz de alguna manera de:

“… [read] el puntero al contador, incrementa el contador y devuelve el puntero, todo de tal manera que ningún otro subproceso puede causar un resultado incorrecto”

Pero realmente no entiendo la forma en que realmente implementa esto. Está usando instrucciones PowerPC (no portátiles) (las primitivas LL/SC lwarx y stwcx) para lograr esto.

El código relevante que hace esto es lo que él llama un “aIandF(incremento atómico y recuperación), que define como:

addr aIandF(addr r1){
  addr tmp;int c;
  do{
    do{
      tmp = *r1;
      if(!tmp)break;
      c = lwarx(tmp);
    }while(tmp != *r1);
  }while(tmp && !stwcx(tmp,c+1));
  return tmp;
};

Aparentemente, addr es un tipo de puntero que apunta al objeto compartido que posee la variable de recuento de referencia.

mi pregunta es:: ¿Esto solo es posible con una arquitectura que admita operaciones LL/SC? Parece que sería imposible hacerlo con cmpxchg. Y en segundo lugar, ¿cómo funciona exactamente esto? He leído este código varias veces y realmente no puedo entender lo que está pasando. entiendo lo que LL/SC las primitivas lo hacen, simplemente no puedo entender el código.

Lo mejor que puedo entender es que addr r1 es la dirección del puntero al objeto compartido, y además la dirección del puntero al recuento de referencia (que supongo que significa que la variable de recuento de referencia debe ser el primer miembro del struct que define el objeto compartido). Luego desreferencia addr (obteniendo la dirección real del objeto compartido). Luego, vinculó cargas el valor almacenado en la dirección en tmpy almacena el resultado en c. Este es el valor del contador. Luego almacena condicionalmente ese valor incrementado (que fallará si tmp ha cambiado) de nuevo en tmp.

Lo que no entiendo es cómo funciona esto. Es posible que la dirección del objeto compartido nunca cambie y el LL/SC podría tener éxito, pero ¿cómo nos ayuda esto si otro subproceso ha desasignado el objeto compartido mientras tanto?

addr aIandF(addr r1) {
  addr tmp;
  int c;
  do {
    do {
      // r1 holds the address of the address
      // of the refcount
      tmp = *r1;       // grab the address of the refcount
      if (!tmp) break; // if it's null, bail

      // read current refcount
      // and acquire reservation
      c = lwarx(tmp);

      // now we hold the reservation,
      // check to see if another thread
      // has changed the shared block address
    } while (tmp != *r1); // if so, start over

    // if the store succeeds we know we held
    // the reservation throughout
  } while (tmp && !stwcx(tmp, c+1));
  return tmp;
};

Tenga en cuenta que aIandF se usa específicamente cuando se construye una copia de un puntero compartido existente, reclamando una referencia para la copia.

El artículo del Dr. Dobbs describe la operación para liberar una referencia como primero intercambiar atómicamente la dirección del contador compartido en el objeto de puntero compartido fuente con un puntero nulo local a la función; luego decrementando atómicamente el contador; luego probando para ver si el resultado del decremento fue cero. Este orden de operaciones es importante: usted dice, “Es posible que la dirección del objeto compartido nunca cambie y el LL/SC podría tener éxito, pero ¿cómo nos ayuda esto si otro subproceso ha desasignado el objeto compartido mientras tanto?” – pero esto nunca puede suceder, ya que el objeto nunca se desasignará sin que ocurra primero el intercambio, lo que nos brinda un medio para observar el cambio de dirección.

aIandF comprueba que la dirección del contador sea nula en la entrada.

Puede detectar que la dirección se vuelve nula si eso ocurre antes de que lwarxporque prueba explícitamente esto una vez que tiene la reserva.

Si el intercambio en el subproceso decreciente ocurre después de lwarx, en realidad no nos importa: si el stwcx en aIandF tiene éxito, sabemos que el subproceso decreciente verá el nuevo recuento de referencias y no destruirá el objeto, y podemos continuar sabiendo que hemos reclamado una referencia a él; mientras que si el otro subproceso logra disminuir el contador primero, perderemos nuestra reserva, la tienda fallará y detectaremos la destrucción del objeto en la siguiente iteración del bucle.

Este algoritmo asume un modelo de memoria fuertemente consistente (todos los subprocesos siempre ven los efectos de las lecturas y escrituras de los demás en el orden del programa); este no es necesariamente el caso incluso en aquellas arquitecturas modernas que admiten ll/sc.

EDIT: pensándolo bien, el algoritmo además aparentemente asume que siempre es seguro leer desde una dirección de memoria que alguna vez fue válida (por ejemplo, sin MMU/protección; o el algoritmo está roto):

if (!tmp) break;

// another thread could, at this point, do its swap, 
// decrement *and* destroy the object tmp points to
// before we get to do anything else

c = lwarx(tmp); 

// if that happened, we'll detect this fact and do nothing with c
// but ONLY if the lwarx doesn't trap 
// (due to the memory tmp points to 
// getting unmapped when the other thread frees the object)