Qu'est-ce qu'une fonction réentrante ?

Question

Le plus de le site temps La définition de la réentrée est citée dans le texte suivant Wikipedia :

Un programme ou une routine informatique est décrit comme réentrant s'il peut être en toute sécurité appelé à nouveau avant que son avant que l'invocation précédente ne soit terminée (c'est-à-dire qu'il peut être exécuté en toute sécurité en même temps). Pour être réentrant, un programme ou routine informatique :

1. Ne doit contenir aucune donnée statique (ou globale) données non constantes.
2. Ne doit pas retourner l'adresse de données statiques (ou globales) non constantes données.
3. Doit travailler uniquement sur les données fournies par l'appelant.
4. Ne doit pas dépendre des verrous sur les ressources ressources.
5. Ne doit pas modifier son propre code (sauf si qu'il ne s'exécute dans son propre unique)
6. Ne doit pas appeler des programmes ou des routines programmes ou routines.

Comment en toute sécurité défini ?

Si un programme peut être exécutés simultanément en toute sécurité cela signifie-t-il toujours qu'il est réentrant ?

Quel est exactement le point commun entre les six points mentionnés que je dois garder à l'esprit lorsque je vérifie les capacités réentrantes de mon code ?

Aussi,

1. Toutes les fonctions récursives sont-elles réentrantes ?
2. Toutes les fonctions thread-safe sont-elles réentrantes ?
3. Toutes les fonctions récursives et thread-safe sont-elles réentrantes ?

---

En écrivant cette question, une chose me vient à l'esprit : Est-ce que les termes comme réentrée y sécurité du fil absolus du tout, c'est-à-dire ont-ils des définitions concrètes fixes ? Car, si ce n'est pas le cas, cette question n'a pas beaucoup de sens.

Answer 1

1. Comment est en toute sécurité défini ?

Sémantiquement. Dans ce cas, il ne s'agit pas d'un terme défini avec précision. Il signifie simplement "Vous pouvez faire cela, sans risque".

2. Si un programme peut être exécuté simultanément en toute sécurité, cela signifie-t-il toujours qu'il est réentrant ?

Non.

Par exemple, prenons une fonction C++ qui prend à la fois un verrou et un rappel en paramètre :

#include <mutex>

typedef void (*callback)();
std::mutex m;

void foo(callback f)
{
    m.lock();
    // use the resource protected by the mutex

    if (f) {
        f();
    }

    // use the resource protected by the mutex
    m.unlock();
}

Une autre fonction pourrait bien avoir besoin de verrouiller le même mutex :

void bar()
{
    foo(nullptr);
}

A première vue, tout semble correct Mais attendez :

int main()
{
    foo(bar);
    return 0;
}

Si le verrou sur le mutex n'est pas récursif, voici ce qui va se passer, dans le thread principal :

1. main appellera foo .
2. foo va acquérir le verrou.
3. foo appellera bar qui appellera foo .
4. le 2e foo va essayer d'acquérir le verrou, échouer et attendre qu'il soit libéré.
5. Impasse.
6. Oups

Ok, j'ai triché, en utilisant le truc du callback. Mais il est facile d'imaginer des morceaux de code plus complexes ayant un effet similaire.

3. Quel est exactement le point commun entre les six points mentionnés que je dois garder à l'esprit lorsque je vérifie les capacités réentrantes de mon code ?

Vous pouvez odeur un problème si votre fonction a/donne accès à une ressource persistante modifiable, ou a/donne accès à une fonction qui odeurs .

( Ok, 99% de notre code devrait sentir, alors Voir la dernière section pour gérer ça )

Ainsi, en étudiant votre code, un de ces points devrait vous alerter :

1. La fonction a un état (c'est-à-dire qu'elle accède à une variable globale, ou même à une variable de classe).
2. Cette fonction peut être appelée par plusieurs threads, ou peut apparaître deux fois dans la pile pendant l'exécution du processus (c'est-à-dire que la fonction peut s'appeler elle-même, directement ou indirectement). Fonction prenant des callbacks comme paramètres odeur beaucoup.

Notez que la non-réentrance est virale : une fonction qui pourrait appeler une éventuelle fonction non-réentrante ne peut être considérée comme réentrante.

Notez également que les méthodes C++ odeur parce qu'ils ont accès à this Il faut donc étudier le code pour s'assurer qu'ils n'ont pas d'interaction bizarre.

4.1. Toutes les fonctions récursives sont-elles réentrantes ?

Non.

Dans les cas multithreads, une fonction récursive accédant à une ressource partagée peut être appelée par plusieurs threads au même moment, ce qui entraîne des données erronées/corrompues.

Dans les cas monofilaires, une fonction récursive pourrait utiliser une fonction non récursive (comme la tristement célèbre strtok ), ou utiliser des données globales sans tenir compte du fait que ces données sont déjà utilisées. Ainsi, votre fonction est récursive car elle s'appelle elle-même directement ou indirectement, mais elle peut toujours être Récursif - non sûr .

4.2. Toutes les fonctions thread-safe sont-elles réentrantes ?

Dans l'exemple ci-dessus, j'ai montré comment une fonction apparemment threadsafe n'était pas réentrante. D'accord, j'ai triché à cause du paramètre callback. Mais alors, il y a de multiples façons de bloquer un thread en lui faisant acquérir deux fois un verrou non récurrent.

4.3. Toutes les fonctions récursives et thread-safe sont-elles réentrantes ?

Je dirais "oui" si par "récursif" vous entendez "sûr par récurrence".

Si vous pouvez garantir qu'une fonction peut être appelée simultanément par plusieurs threads, et peut s'appeler elle-même, directement ou indirectement, sans problème, alors elle est réentrante.

Le problème est d'évaluer cette garantie ^_^

5. Les termes tels que réentrée et sécurité des fils sont-ils absolus, c'est-à-dire ont-ils des définitions concrètes fixes ?

Je crois qu'ils le font, mais évaluer si une fonction est thread-safe ou réentrante peut être difficile. C'est pourquoi j'ai utilisé le terme odeur ci-dessus : Vous pouvez trouver qu'une fonction n'est pas réentrante, mais il peut être difficile d'être sûr qu'un morceau de code complexe est réentrant.

6. Un exemple

Disons que vous avez un objet, avec une méthode qui doit utiliser une ressource :

struct MyStruct
{
    P * p;

    void foo()
    {
        if (this->p == nullptr)
        {
            this->p = new P();
        }

        // lots of code, some using this->p

        if (this->p != nullptr)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

Le premier problème est que si, d'une manière ou d'une autre, cette fonction est appelée de façon récursive (c'est-à-dire que cette fonction s'appelle elle-même, directement ou indirectement), le code se plantera probablement, car this->p sera supprimé à la fin du dernier appel, et sera probablement encore utilisé avant la fin du premier appel.

Ainsi, ce code n'est pas récursif-sécurisé .

Nous pourrions utiliser un compteur de référence pour corriger cela :

struct MyStruct
{
    size_t c;
    P * p;

    void foo()
    {
        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        // lots of code, some using this->p
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

De cette façon, le code devient récursif-sécurisé Mais il n'est toujours pas réentrant à cause des problèmes de multithreading : Nous devons être sûrs que les modifications de c et de p se fera de manière atomique, en utilisant un récursif mutex (tous les mutex ne sont pas récursifs) :

#include <mutex>

struct MyStruct
{
    std::recursive_mutex m;
    size_t c;
    P * p;

    void foo()
    {
        m.lock();

        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        m.unlock();
        // lots of code, some using this->p
        m.lock();
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }

        m.unlock();
    }
};

Et bien sûr, tout cela suppose que le lots of code est lui-même ré-entrant, y compris l'utilisation de p .

Et le code ci-dessus n'est pas du tout à l'abri des exceptions mais c'est une autre histoire ^_^

7. Hey 99% de notre code n'est pas réentrant !

C'est tout à fait vrai pour le code spaghetti. Mais si vous partitionnez correctement votre code, vous éviterez les problèmes de réentrance.

7.1. Assurez-vous que toutes les fonctions n'ont PAS d'état

Elles ne doivent utiliser que les paramètres, leurs propres variables locales, les autres fonctions sans état, et renvoyer des copies des données si elles en renvoient.

7.2. Assurez-vous que votre objet est "recursive-safe".

Une méthode objet a accès à this Il partage donc un état avec toutes les méthodes de la même instance de l'objet.

Assurez-vous donc que l'objet peut être utilisé à un moment donné de la pile (c'est-à-dire en appelant la méthode A), puis à un autre moment (c'est-à-dire en appelant la méthode B), sans corrompre l'ensemble de l'objet. Concevez votre objet pour vous assurer qu'à la sortie d'une méthode, l'objet est stable et correct (pas de pointeurs qui pendent, pas de variables membres contradictoires, etc.)

7.3. Assurez-vous que tous vos objets sont correctement encapsulés

Personne d'autre ne devrait avoir accès à leurs données internes :

    // bad
    int & MyObject::getCounter()
    {
        return this->counter;
    }

    // good
    int MyObject::getCounter()
    {
        return this->counter;
    }

    // good, too
    void MyObject::getCounter(int & p_counter)
    {
        p_counter = this->counter;
    }

Même le fait de renvoyer une référence const peut être dangereux si l'utilisateur récupère l'adresse des données, car une autre partie du code pourrait la modifier sans que le code détenant la référence const en soit informé.

7.4. Assurez-vous que l'utilisateur sait que votre objet n'est pas thread-safe.

Ainsi, l'utilisateur est responsable de l'utilisation des mutex pour utiliser un objet partagé entre les threads.

Les objets de la STL sont conçus pour ne pas être thread-safe (à cause de problèmes de performance), et donc, si un utilisateur veut partager un fichier std::string entre deux threads, l'utilisateur doit protéger son accès avec des primitives de concurrence ;

7.5. Assurez-vous que votre code thread-safe est recursif-safe.

Cela signifie utiliser des mutex récursifs si vous pensez que la même ressource peut être utilisée deux fois par le même thread.

Answer 2

Le terme "en toute sécurité" est défini exactement comme l'indique le bon sens - il signifie "faire son travail correctement sans interférer avec d'autres choses". Les six points que vous citez expriment très clairement les exigences pour y parvenir.

La réponse à vos 3 questions est 3× "non".

---

Toutes les fonctions récursives sont-elles réentrantes ?

NON !

Deux invocations simultanées d'une fonction récursive peuvent facilement se perturber mutuellement, si elles accèdent aux mêmes données globales/statiques, par exemple.

---

Toutes les fonctions thread-safe sont-elles réentrantes ?

NON !

Une fonction est thread-safe si elle ne présente pas de dysfonctionnement si elle est appelée simultanément. Mais cela peut être réalisé, par exemple, en utilisant un mutex pour bloquer l'exécution de la deuxième invocation jusqu'à ce que la première se termine, de sorte qu'une seule invocation fonctionne à la fois. La réentrance signifie s'exécutant simultanément sans interférer avec d'autres invocations .

---

Toutes les fonctions récursives et thread-safe sont-elles réentrantes ?

NON !

Voir ci-dessus.

Answer 3

Le fil conducteur :

Le comportement est-il bien défini si la routine est appelée alors qu'elle est interrompue ?

Si vous avez une fonction comme celle-ci :

int add( int a , int b ) {
  return a + b;
}

Il ne dépend donc d'aucun état extérieur. Le comportement est bien défini.

Si vous avez une fonction comme celle-ci :

int add_to_global( int a ) {
  return gValue += a;
}

Le résultat n'est pas bien défini sur plusieurs fils. Des informations peuvent être perdues si le moment est mal choisi.

La forme la plus simple d'une fonction réentrante est quelque chose qui opère exclusivement sur les arguments passés et les valeurs constantes. Tout le reste nécessite une manipulation spéciale ou, souvent, n'est pas réentrant. Et bien sûr, les arguments ne doivent pas faire référence à des globaux mutables.

Answer 4

Je dois maintenant développer mon commentaire précédent. La réponse de @paercebal est incorrecte. Dans l'exemple de code, personne n'a remarqué que le mutex qui est censé être un paramètre n'est pas réellement passé ?

Je conteste la conclusion, je l'affirme : pour qu'une fonction soit sûre en présence de concurrence, elle doit être ré-entrante. Par conséquent, concurrent-safe (généralement écrit thread-safe) implique re-entrant.

Ni le thread safe ni le re-entrant n'ont rien à dire sur les arguments : nous parlons de l'exécution concurrente de la fonction, qui peut toujours être non sûre si des paramètres inappropriés sont utilisés.

Par exemple, memcpy() est thread-safe et re-entrant (généralement). Il est évident qu'il ne fonctionnera pas comme prévu s'il est appelé avec des pointeurs vers les mêmes cibles à partir de deux threads différents. C'est l'intérêt de la définition de la SGI, qui fait reposer sur le client la responsabilité de s'assurer que les accès à la même structure de données sont synchronisés par le client.

Il est important de comprendre qu'en général, c'est bêtises pour que les paramètres soient inclus dans les opérations à sécurité thread. Si vous avez fait de la programmation de base de données, vous comprendrez. Le concept de ce qui est "atomique" et pourrait être protégé par un mutex ou une autre technique est nécessairement un concept d'utilisateur : le traitement d'une transaction sur une base de données peut nécessiter de multiples modifications ininterrompues. Qui peut dire lesquelles doivent être maintenues en synchronisation si ce n'est le programmeur du client ?

Le fait est que la "corruption" n'est pas forcément le fait d'endommager la mémoire de votre ordinateur avec des écritures non sérialisées : la corruption peut toujours se produire même si toutes les opérations individuelles sont sérialisées. Il s'ensuit que lorsque vous demandez si une fonction est thread-safe ou ré-entrante, la question s'applique à tous les arguments séparés de manière appropriée : l'utilisation d'arguments couplés ne constitue pas un contre-exemple.

Il existe de nombreux systèmes de programmation : Ocaml en est un, et je pense que Python aussi, qui contiennent beaucoup de code non réentrant, mais qui utilisent un verrou global pour intercaler les accès aux threads. Ces systèmes ne sont pas réentrants et ne sont pas thread-safe ou concurrent-safe, ils fonctionnent de manière sûre simplement parce qu'ils empêchent la concurrence de manière globale.

Un bon exemple est malloc. Il n'est pas ré-entrant et n'est pas thread-safe. Cela est dû au fait qu'il doit accéder à une ressource globale (le tas). L'utilisation de verrous ne le rend pas sûr : il n'est certainement pas ré-entrant. Si l'interface de malloc avait été conçue correctement, il aurait été possible de la rendre ré-entrante et thread-safe :

malloc(heap*, size_t);

Maintenant, il peut être sûr parce qu'il transfère au client la responsabilité de sérialiser l'accès partagé à un seul tas. En particulier, aucun travail n'est nécessaire s'il y a des objets heap séparés. Si un tas commun est utilisé, le client doit sérialiser l'accès. Utilisation d'un verrou à l'intérieur de la fonction ne suffit pas : il suffit de considérer un malloc verrouillant un heap* et ensuite un signal arrive et appelle malloc sur le même pointeur : deadlock : le signal ne peut pas continuer, et le client ne peut pas non plus car il est interrompu.

D'une manière générale, les verrous ne rendent pas les choses plus sûres ils détruisent en fait la sécurité en essayant de gérer de manière inappropriée une ressource qui est la propriété du client. Le verrouillage doit être effectué par le fabricant de l'objet, qui est le seul code à savoir combien d'objets sont créés et comment ils seront utilisés.

Answer 5

Le "fil conducteur" (jeu de mots !?) parmi les points énumérés est que la fonction ne doit rien faire qui puisse affecter le comportement de tout appel récursif ou concurrent à la même fonction.

Ainsi, par exemple, les données statiques posent problème car elles appartiennent à tous les threads ; si un appel modifie une variable statique, tous les threads utilisent les données modifiées, ce qui affecte leur comportement. Le code auto-modifiant (bien que rarement rencontré, et dans certains cas évité) serait un problème, car bien qu'il y ait plusieurs threads, il n'y a qu'une seule copie du code ; le code est aussi une donnée statique essentielle.

Essentiellement, pour être ré-entrant, chaque thread doit pouvoir utiliser la fonction comme s'il était le seul utilisateur, ce qui n'est pas le cas si un thread peut affecter le comportement d'un autre de manière non déterministe. Cela implique principalement que chaque thread dispose de données distinctes ou constantes sur lesquelles la fonction travaille.

Cela dit, le point (1) n'est pas nécessairement vrai ; par exemple, vous pourriez légitimement et par conception utiliser une variable statique pour conserver un compte de récurrence afin de vous prémunir contre une récurrence excessive ou pour profiler un algorithme.

Une fonction thread-safe n'a pas besoin d'être réentrante ; elle peut réaliser la thread safety en empêchant spécifiquement la réentrance avec un verrou, et le point (6) dit qu'une telle fonction n'est pas réentrante. En ce qui concerne le point (6), une fonction qui appelle une fonction thread-safe qui se verrouille n'est pas sûre pour une utilisation en récursion (elle se verrouillera), et n'est donc pas dite réentrante, bien qu'elle puisse néanmoins être sûre pour la concurrence, et serait toujours réentrante dans le sens où plusieurs threads peuvent avoir leurs compteurs de programme dans une telle fonction simultanément (juste pas avec la région verrouillée). Peut-être que cela aide à distinguer la thread-safety de la ré-entrance (ou peut-être ajoute-t-il à votre confusion !).