Synchronisation et granularité – Programmation par preuves

Ce qui suit est une « invention » personnelle, sorte d'idiome de programmation maison, développé pour résoudre des problèmes rencontrés dans certains de mes projets. Je ne doute cependant pas que d'autres y aient pensé aussi ailleurs dans le monde. Si vous avez vent de pratiques semblables ailleurs, de même que des noms utilisés pour les décrire, faites-moi signe!

Si vous cherchez plutôt des informations sur la preuve au sens mathématique du terme, voir ../Maths/Preuve.html.

Que signifie être Thread-Safe pour un conteneur? Certains semblent croire que la question est banale, mais s'il est généralement admis qu'une opération comme c.add(e) ou c.push_back(e) – en fonction des langages ou des pratiques – d'un élément e dans un conteneur c pourrait raisonnablement être synchronisée, qu'en est-il de l'application d'algorithmes en général, par exemple une recherche dichotomique?

Le problème en est un de granularité : le code client sait ce qu'il souhaite faire mais le conteneur devrait être responsable de la synchronisation des opérations sur ses données. Ajouter une méthode comme get_mutex() sur un conteneur remettrait la responsabilité de la synchronisation entre les mains du code client, et serait un signe clair que quelque chose ne va pas... Un Bad Code Smell.

Programmer par preuves

Une solution au dilemme résultant du fait que la granularité des opérations est du domaine du code client alors que la responsabilité de la saine synchronisation des opérations incombe au code serveur (le conteneur dans ce cas-ci) est la programmation par preuves.

L'idée générale est simple :

Ce faisant, le serveur synchronise mais le code client détermine la gamme d'opérations à faire pendant la période où la synchronisation est effective. Notez qu'un client mal venu pourrait paralyser un serveur en réalisant, pendant cette période, des opérations telles qu'une boucle infinie, mais il s'agit là des aléas de la technique.

Un prenant une classe X générale à titre de conteneur, voici comment la technique s'articulerait :

  • la classe X offre des opérations nécessitant de la synchronisation, ici représentées par la méthode oper();
  • la preuve de synchronisation pour X sera une classe interne et privée. Ici, cette classe se nomme Preuve;
  • chaque méthode de la classe X qui nécessitera de la synchronisation, incluant oper(), prendra en paramètre une instance anonyme de Preuve;
  • un client passant une Preuve en paramètre à une méthode garantit avoir synchronisé les accès au préalable;
  • une méthode générique, ici appliquer(), prend en paramètre un opération binaire (à deux paramètres) générique, ici fct, du type F. Il est très probable que F soit un foncteur (du moins, en C++, F le sera nécessairement);
  • la méthode appliquer() synchronise, par une approche RAII, les accès aux ressources de l'instance de X et applique sur cette instance l'opération fct. Le second paramètre passé à cette opération est une instance de Preuve.
class X
{
   // ...
   std::mutex mutex_; // ou autre
   class Preuve {};
public:
   template <class F>
      F appliquer(F fct)
      {
         std::lock_guard<std::mutex> verrou(mutex_);
         fct(*this, Preuve{});
         return fct;
      }
   void oper(Preuve)
   {
      // ... opérer sur *this
   }
   // ...
};

En quoi cela solutionne-t-il le problème de la granularité de la synchronisation? Voici :

Un exemple de code client serait le foncteur operer, décrit à droite :

  • il expose un opérateur () générique sur la base d'un type P (pour Preuve), inconnu a priori et qui n'est utilisé que pour signaler aux méthodes de l'objet x que le foncteur possède la preuve de synchronisation; et
  • il passe cette preuve aux méthodes qui l'exigent. Le client effectif de la méthode operator() est la classe X, qui sait instancier la preuve, ce qui rend l'invocation du foncteur valide.
struct operer
{
   template <class P>
      void operator()(X &x, P preuve)
      {
         // utiliser x en passant preuve
         // à ses méthodes, p. ex. :
         x.oper(preuve);
      }
};

Un exemple d'utilisation d'un X à l'aide d'une instance de l'opération operer serait :

void operer_avec_synchro(X &x)
{
   x.appliquer(operer());
}

Le cheminement de l'information et des responsabilités va comme suit :

Notez que le foncteur operer ne peut pas entreposer preuve pour usage futur (du moins pas de manière utilisable) car le type P n'est pas connu au niveau du type operer; la connaissance de P se limite à la méthode operator() pour une instanciation donnée de cette méthode.

Une faille perverse (et sa solution)

L'idée derrière le terme Skeleton Key est celle d'une clé capable d'ouvrir tous les coffres.

Ce mécanisme est sécuritaire si le type servant de preuve ne peut être contrefait. Cependant, dans la forme proposée plus haut, il est possible de créer un type capable de se faire passer pour un X::Preuve même si ce type est inaccessible au code client.

L'idée qui suit est de Colin Towle, étudiant à la cohorte 05 du DDJV à l'Université de Sherbrooke.

Cette proposition repose sur l'idée d'un type, que nous nommerons skeleton_key, capable de se faire passer implicitement pour une instance de tout autre type (du moins, ceux ayant un constructeur par défaut) sans connaître la sémantique ou les détails de ces types.

struct skeleton_key
{
   template <class T>
      operator T() const
         { return T{}; }
};

La proposition est simple : un type offrant un opérateur de conversion implicite en T pour un type T, et qui retournerait un T quelconque plutôt que de réaliser une véritable conversion.

Un opérateur de conversion implicite dit au compilateur comment il est possible de « convertir » une instance d'un type à une instance d'un autre type. Par exemple :

#include <string>
#include <iostream>
using namespace std;
struct Trois
{
   operator int() const
      { return 3; }
   operator std::string() const
      { return "Trois"; }
};
int main()
{
   Trois trois;
   int i = trois; // i == 3
   string s = trois; // s == "Trois"
   cout << trois; // ambigu : convertir en int ou en string?
}

À titre d'exemple, l'expression proposée à droite initialiserait i à la valeur zéro puisque :

  • L'expression skeleton_key() construit un skeleton_key anonyme
  • Le compilateur ne sait pas comment affecter ce skeleton_key à un int
  • Le moteur d'inférence du compilateur constate qu'il est par contre en mesure de générer implicitement un int à partir d'un skeleton_key grâce à son opérateur de conversion en int (en fait, en T avec int pour type T)
  • Ce faisant, l'étape intermédiaire de conversion du skeleton_key en int est réalisée par le moteur d'inférence, ce qui mène à l'instanciation d'un int par défaut (int(), donc zéro) et à l'initialisation de la variable i à partir de cette valeur
// ...
int i = skeleton_key{};
// ...

En quoi la skeleton_key met-elle en danger la mécanique de sécurisation par preuves proposée plus haut? En fait, notre mécanisme dépend de l'incapacité de falsifier la preuve, ce que permet malheureusement de faire skeleton_key dans la forme « vanille » de notre stratégie.

Examinons en effet l'extrait de code à droite. On y voit la fonction vilain() appeler la méthode oper() d'une instance x de X en lui passant non pas une X::Preuve, type qui lui est inaccessible de toute manière, mais bien une instance de skeleton_key.

Bien entendu, le compilateur ne trouvera pas de méthode X::oper(skeleton_key). Le moteur d'inférence de types prendra alors en charge le processus et cherchera à voir s'il est possible de trouver une méthode X::oper(T) telle qu'il existe une conversion implicite de skeleton_key en T.

Évidemment, cette méthode existe : il s'agit de X::oper(Preuve), précisément!

void vilain(X &x)
{
   x.oper(skeleton_key{}); //oups!
}

Conséquence : le compilateur générera la conversion manquante pour nous, sans que nous n'ayons à injecter dans skeleton_key la connaissance du type dans lequel la conversion sera réalisée, et la protection sera brisée.

Heureusement, il existe une solution relativement simple : empêcher l'instanciation d'un X::Preuve par qui que ce soit d'autre que X ou que X::Preuve. Ici, skeleton_key parvient à se faire convertir en X::Preuve parce que le compilateur a accès au constructeur par défaut de ce type. Il nous faut donc bloquer ce constructeur, sans toutefois bloquer le constructeur de copie (que nous utilisons pour passer une X::Preuve aux divers services de X).

Cette sécurisation se fait en deux temps :

  • Le constructeur par défaut de X::Preuve doit être explicitement déclaré privé, pour éviter que le compilateur ne puisse en générer un spontanément qui soit public, et
  • La classe X doit être amie de X::Preuve pour être en mesure de l'instancier malgré tout
class X
{
   class Preuve
   {
      Preuve() = default; // privé
      friend class X;
   };
   // ...
   std::mutex mutex_;
public:
   template <class F>
      F appliquer(F fct)
      {
         std::lock_guard<std::mutex> verrou{mutex_};
         fct(*this, Preuve{}); // Ok: X est ami de X::Preuve
         return fct;
      }
   // ...
};

Voilà, le tour est joué!

En 2015, le chic Maxime Turmel m'a écrit pour me proposer cette variante du skeleton_key :

struct skeleton_key {
   template <class T>
      operator T() const {
         T* t = nullptr;
         return *t; 
      }
}; 

Cette approche perverse visait à ne pas avoir besoin d'appeler un constructeur de T pour retourner le T, et contourner ainsi le constructeur par défaut privé de Preuve.

Bien qu'il se peuve que cette approche fonctionne en pratique, notez que déréférencer un pointeur nul, même si ce n'est pas pour accéder aux membres d'un objet inexistant, est un cas patent de comportement indéfini, alors on ne peut pas considérer ceci comme un contournement légitime. Ça reste amusant, cela dit  .


Valid XHTML 1.0 Transitional

CSS Valide !