Comptage de références sans verrouillage et pointeurs intelligents C ++

Question

En général, la plus connue des implémentations de référence-comptage intelligent ptr classes en C++, y compris la norme std::shared_ptr, l'utilisation atomique de comptage de référence, mais ne fournissent pas d'accès atomique à la même puce, ptr instance. En d'autres termes, plusieurs threads peuvent fonctionner en toute sécurité sur des shared_ptr des cas qui pointent vers le même objet partagé, mais plusieurs threads ne peuvent pas sûre de lire/écrire des instances de la même shared_ptr de l'instance sans fournir une sorte de synchronisation comme un mutex ou quoi que ce soit.

Atomique version d'un shared_ptr appelé "atomic_shared_ptr" a été proposé, et les premiers implémentations existent déjà. Sans doute, atomic_shared_ptr pourrait facilement être mis en œuvre avec un verrou de rotation ou d'un mutex, mais sans verrouillage de la mise en œuvre est également possible.

Après l'étude de certaines de ces oeuvres, une chose est évidente: la mise en œuvre d'un lock-libre - std::shared_ptr est très difficile, et il semble qu'besoin de tant compare_and_exchange des opérations de me faire question de savoir si un simple verrou de rotation permettrait d'atteindre de meilleures performances.

La principale raison pour laquelle il est si difficile à mettre en œuvre un sans verrouillage de référence compté pointeur est en raison de la race qui existe toujours entre la lecture partagée bloc de contrôle (ou de l'objet partagé lui-même, si nous parlons d'un intrusif pointeur partagé), et en modifiant le nombre de références.

En d'autres termes, vous ne pouvez même pas sûre de lire le compteur de référence parce que vous ne savez jamais quand un autre thread a libéré la mémoire où le nombre de références vie.

Donc, en général, complexes et diverses stratégies sont employées pour créer un verrouillage des versions gratuites. La mise en œuvre ici dirait qu'il utilise un double comptage de référence de la stratégie, où il y a des "locaux", les références qui permettent de compter le nombre de threads simultanément accès à l' shared_ptr instance, puis "partagé" ou "global" des références qui permettent de compter le nombre de shared_ptr instances de pointage de l'objet partagé.

Compte tenu de cette complexité, j'ai été vraiment surpris de trouver un Dr Dobbs article, à partir de 2004 , pas moins (chemin avant C++11 atomics) qui semble nonchalamment résoudre ce problème:

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

Il ressemble à l'auteur prétend en quelque sorte être en mesure de:

"... [lire] le pointeur vers le compteur incrémente le compteur, et retourne le pointeur-ensemble de telle manière qu'aucun autre thread peut provoquer un résultat incorrect"

Mais je ne comprends pas vraiment la façon dont il fait la met en œuvre. Il utilise (non portable) processeur PowerPC instructions (le LL/SC primitives lwarx et stwcx) pour tirer cette off.

Le code qui est fait, est ce qu'il appelle un "aIandF" (atomique d'incrémentation et de chercher), qu'il définit comme:

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;
};

Apparemment, addr est un type de pointeur pointant sur l'objet partagé qui détient le compte de référence variable.

Ma question est: est-ce seulement possible de le faire avec une architecture qui prend en charge LL/SC opérations? Il semble qu'il serait impossible de le faire avec cmpxchg. Et deuxièmement, exactement comment cela fonctionne? J'ai lu sur ce code quelques temps maintenant, et je ne peux pas vraiment comprendre ce qu'il se passe. Je comprends ce que LL/SC primitives de le faire, je ne peux pas faire tout les sens du code.

Le mieux que je peux comprendre, c'est qu' addr r1 est l'adresse du pointeur de l'objet partagé, et aussi l'adresse du pointeur pour le compte de référence (qui je suppose signifie que le compteur de référence de la variable doit être le premier membre de l' struct qui définit l'objet partagé). Il a ensuite déréférence addr (obtenir l'adresse réelle de l'objet partagé). Ensuite, il a lié les charges de la valeur stockée à l'adresse en tmp, et stocke le résultat dans c. C'est la valeur du compteur. Il a ensuite conditionnellement stocke cette valeur incrémentée (qui échouera si tmp a changé) en tmp.

Ce que je ne comprends pas, c'est comment cela fonctionne. L'adresse de l'objet partagé ne peut jamais changer et le LL/SC pourrait réussir - mais comment est-ce à nous aider si un autre thread a libéré l'objet partagé dans le temps de le dire?

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;
};

Notez que aIandF est utilisé en particulier lors de la construction d'une copie d'un pointeur partagé, revendiquant une référence pour la copie.

Le Dr Dobbs article décrit l'opération pour libérer une référence en tant que premier atomiquement permutation de l'adresse de l'partagée compteur dans la source pointeur partagé objet avec un pointeur null locale à la fonction; puis atomiquement décrémenter le compteur; puis test pour voir si le résultat de la diminution était de zéro. Cet ordre est important: vous dites, "l'adresse de L'objet partagé ne peut jamais changer et le LL/SC pourrait réussir - mais comment est-ce à nous aider si un autre thread a libéré l'objet partagé dans le temps de le dire?" - mais cela ne peut jamais arriver, car l'objet ne sera jamais libéré sans le swap qui se passe d'abord, de nous donner les moyens d'observer le changement d'adresse.

aIandF tests pour le compteur d'adresse étant nulle à l'entrée.

Il peut repérer l'adresse à devenir nul si cela se produit avant l' lwarx, parce que c'explicitement tests pour cette fois il a de la réserve.

Si le swap dans la décrémentation de fil se produit après la lwarx nous n'avons pas réellement de soins: si l' stwcx en aIandF réussit, nous savons que la décrémentation de thread va voir le nouveau compteur de référence et de ne pas détruire l'objet, et nous pouvons procéder sachant que nous avons demandé une référence à elle; que, si l'autre thread réussit à décrémenter le compteur d'abord, nous allons perdre notre réservation, le magasin va échouer et nous allons détecter la destruction de l'objet sur la prochaine itération de boucle.

Cet algorithme suppose une cohérence forte du modèle de mémoire (tous les threads toujours voir les effets des uns et des autres lectures et écritures dans le programme de commande) - ce n'est pas nécessairement le cas, même sur les architectures modernes qui ne soutien ll/sc.

EDIT: réflexion à ce sujet, l'algorithme aussi apparemment fait l'hypothèse qu'il est toujours plus sûr de les lire à partir d'une adresse mémoire qui a été une fois valide (par exemple, pas de MMU/protection; ou, l'algorithme est cassé):

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)