tipos - que es un parametro en c++

Recuento de referencias sin bloqueo y punteros inteligentes de C++

Question

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

Se ha proposed una versión atómica de un shared_ptr llamado " atomic_shared_ptr ", y ya existen implementations preliminares. Presumiblemente, atomic_shared_ptr podría implementarse fácilmente con un bloqueo de giro o atomic_shared_ptr , pero también es posible una implementación sin bloqueo.

Después de estudiar algunas de estas implementaciones, una cosa es obvia: implementar un std::shared_ptr sin std::shared_ptr es muy difícil y parece que requiere muchas operaciones de compare_and_exchange 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 sin referencias de bloqueo es debido a la carrera que siempre existe entre la lectura del bloque de control compartido (o el objeto compartido mismo, si estamos hablando de un puntero compartido intrusivo), y modificando el recuento de referencia.

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

Entonces, en general, se emplean varias estrategias complejas para crear versiones sin bloqueo. La implementations parece que utiliza una estrategia de conteo de doble referencia, donde hay referencias "locales" que cuentan el número de subprocesos que acceden simultáneamente a la instancia shared_ptr , y luego referencias "compartidas" o "globales" que cuentan el número de instancias de shared_ptr apuntando al objeto compartido.

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

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

Parece que el autor afirma que de alguna manera podrá:

"... [lee] 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) (los primitivos LL / SC, lwarx y stwcx ) para lograr esto.

El código relevante que hace esto es lo que él llama " 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 conteo de referencia.

Mi (s) pregunta (s) es : ¿esto es posible solo con una arquitectura que admita operaciones de LL / SC? Parece que sería imposible hacerlo con cmpxchg . Y en segundo lugar, ¿cómo funciona esto exactamente? He leído este código varias veces y no puedo entender lo que está pasando. Entiendo lo que hacen las primitivas LL/SC , 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 también la dirección del puntero al conteo de referencia (lo que supongo significa que la variable de conteo de referencia debe ser el primer miembro de la struct que define el objeto compartido). Luego elimina referencias a addr (obteniendo la dirección real del objeto compartido). Luego, el vinculado carga el valor almacenado en la dirección en tmp y almacena el resultado en c . Este es el valor del contador. Luego almacena condicionalmente ese valor incrementado (que fallará si tmp ha cambiado) nuevamente en tmp .

Lo que no entiendo es cómo funciona esto. La dirección del objeto compartido nunca puede cambiar y el LL / SC podría tener éxito, pero ¿cómo nos ayuda esto si otra hebra ha desasignado el objeto compartido mientras tanto?

Answer 1

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 al construir 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 primer intercambio atómico de la dirección del contador compartido en el objeto puntero compartido de origen con un puntero nulo local a la función; entonces decrementando atómicamente el contador; luego probando si el resultado del decremento fue cero. Este orden de operaciones es importante: usted dice: "La dirección del objeto compartido nunca puede cambiar y la 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 será desasignado sin que ocurra primero el intercambio, lo que nos brinda un medio para observar el cambio de dirección.

aIandF comprueba si la dirección del contador es nula en la entrada.

Puede detectar que la dirección se vuelva nula si eso ocurre antes del lwarx , ya que explícitamente lo prueba una vez que tiene la reserva.

Si el intercambio en el hilo de disminución se produce después del lwarx, no nos importa: si el stwcx en aIandF tiene éxito, sabemos que el hilo de disminución verá el nuevo recuento de referencia y no destruirá el objeto, y podemos continuar sabiendo que hemos reclamado un referencia a ella mientras que si el otro hilo logra disminuir primero el contador, 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 muy consistente (todos los subprocesos siempre ven los efectos de las lecturas y escrituras de los demás en el orden del programa), esto no es necesariamente el caso incluso en aquellas arquitecturas modernas que sí admiten ll / sc.

EDITAR: pensando en ello, el algoritmo también 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)