Synchronisation et granularité – Programmation par preuves

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 :

• Le code serveur, plutôt que d'exposer des services synchronisés à la pièce, offre des services qui ne peuvent être utilisés que si une preuve de synchronisation au préalable est fournie par le code client
• La seule preuve acceptable ne peut être générée que par le serveur lui-même
• Le serveur accepte des opérations génériques, auxquelles il supplée la preuve de synchronisation une fois seulement que cette synchronisation ait été faite, de manière RAII (pour raisons de sécurité)

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.

class X {
   // ...
   std::mutex m; // ou autre
   class Preuve {};
public:
   template <class F>
      F appliquer(F fct) {
         std::lock_guard<std::mutex> verrou{ m };
         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 :

• La seule classe capable d'instancier la classe X::Preuve est X, puisque X::Preuve n'est visible qu'à X
• La seule manière d'instancier une Preuve est de passer par appliquer(), qui prend soin de synchroniser les accès aux ressources
• L'approche RAII garantit l'éventuelle libération de l'outil de synchronisation. Il ne pourrait pas être sécuritaire d'accepter une opération F quelquelconque autrement (en cas de levée d'exception, l'outil de synchronisation pourrait ne jamais être relâché)
• Conséquemment, une méthode exigeant une Preuve ne peut donc être invoquée que si la synchronisation a été mise en place
• La granularité des opérations est sous la responsabilité du code client, puisque l'opération appliquée à travers appliquer() est une opération arbitraire. Évidemment, un client envahissant pourrait prendre le contrôle de l'instance de X pour une longue période... rien n'est parfait

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 :

• La fonction operer_avec_synchro() souhaite appeler x.oper() de manière synchronisée
• Pour ce faire, operer_avec_synchro() crée un operer() qui pourra être rappelé avec le x est une preuve de synchronisation, et passe cet objet anonyme à x. À ce stade, operer_avec_synchro() est client de x
• La méthode x.appliquer() reçoit une instance de operer à titre de foncteur fct. Dans appliquer(), x obtient un std::mutex de manière RAII, assurant ainsi la synchronisation des opérations sur x, puis instancie une X::Preuve et appelle fct() en lui passant une référence sur lui-même et la preuve de synchronisation. À ce stade, x est client de fct
• Puisque le point d'appel de fct est une méthode de X, le type X::Preuve y est accessible. Les templates de C++ sont générés au point d'appel, ce qui rend la génération de la méthode operer::operator(X&,X::Preuve) légale même si X::Preuve n'est pas accessible du point de vue du type operer
• Dans operer::operator(x,preuve) où preuve est de type X::Preuve, le paramètre preuve peut être utilisé pour accéder aux services de x en démontrant que ces accès sont synchronisés (par x, rien de moins!)

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)

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.

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

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.

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

// ...
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.

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).

class X {
   class Preuve {
      Preuve() = default; // privé
      friend class X;
   };
   // ...
   std::mutex m;
public:
   template <class F>
      F appliquer(F fct) {
         std::lock_guard<std::mutex> verrou{ m };
         fct(*this, Preuve{}); // Ok: X est ami de X::Preuve
         return fct;
      }
   // ...
};

Voilà, le tour est joué!

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

Ajustement depuis C++ 11

La technique décrite ci-dessus fonctionne parce que le code client ne peut nommer le type Preuve... mais depuis C++ 11, il est possible de contourner ce « problème » car l'obligation de nommer le type n'en est plus une (à moins de faire un petit ajustement).

En effet, là où il fallait traditionnellement nommer le type pour l'instancier, il est désormais possible de l'instancier par défaut sans cette contrainte :

class X {
   // ...
   std::mutex m; // ou autre
   class Preuve {
      Preuve() = default;
      friend class X;
   };
public:
   template <class F>
      F appliquer(F fct) {
         std::lock_guard<std::mutex> verrou{ m };
         fct(*this, Preuve{});
         return fct;
      }
   void oper(Preuve) {
      // ... opérer sur *this
   }
   // ...
};
int main() {
   X x;
   x.appliquer([](X &){ /* ... */ }); // Ok
   // x.oper(X::Preuve{}); // illégal (nom inaccessible)
}

class X {
   // ...
   std::mutex m; // ou autre
   class Preuve {
      Preuve() = default;
      friend class X;
   };
public:
   template <class F>
      F appliquer(F fct) {
         std::lock_guard<std::mutex> verrou{ m };
         fct(*this, Preuve{});
         return fct;
      }
   void oper(Preuve) {
      // ... opérer sur *this
   }
   // ...
};
int main() {
   X x;
   x.appliquer([](X &){ /* ... */ }); // Ok
   // x.oper(X::Preuve{}); // illégal (nom inaccessible)
   x.oper({}); // oups! Légal!
}

Si cette ouverture n'est pas souhaitée, il faut qualifier d'explicit le constructeur de la Preuve, ce qui imposera de nommer ce type pour l'instancier :

class X {
   // ...
   class Preuve {
      Preuve() = default;
      friend class X;
   };
   // ...
};

class X {
   // ...
   class Preuve {
      explicit Preuve() = default;
      friend class X;
   };
   // ...
};

Lectures complémentaires

Quelques liens pour enrichir le propos :

• En 2021, Raymond Chen explique l'impact de C++ 11 sur cette technique : https://devblogs.microsoft.com/oldnewthing/20210719-00/?p=105454
• Texte de Jonathan Müller en 2022 sur des variantes de cette technique : https://www.foonathan.net/2022/11/proof-types/
• En 2023, Arne Mertz décrit cette technique : https://accu.org/journals/overload/31/176/mertz/