Une API de coroutines pour le langage C

Dans le premier opus [1], nous avons abordé de manière détaillée le code bas niveau permettant la mise en œuvre de flux d'exécution multiples avec les fonctions get/make/swapcontext() de la glibc. Ce nouvel article présente une API de haut niveau pour le C s'appuyant sur les précédentes fonctions, afin de proposer des fonctionnalités avancées de création de coroutines similaires à ce qu'on peut trouver en natif dans d'autres langages.

1. Vue d'ensemble

1.1 Présentation de l'API

L'API se nomme CRTN, raccourci de « CoRouTiNe ». C'est une librairie partagée (libcrtn.so) dynamiquement liée aux applications. Les services fournis s'inspirent de ceux de la librairie pthread. C'est une couche d'abstraction sur les fonctions de la glibc étudiées en détail dans le précédent article [1]. La figure 1 schématise l'architecture.

Le fichier d'interface est <crtn.h>. Tous les noms de types et services sont préfixés par crtn_.

Une coroutine est créée avec la fonction crtn_spawn(). Un identifiant de coroutine de type crtn_t est retourné à l'utilisateur. Il est utilisé comme référence pour les autres services. Une coroutine récupère son identifiant avec le service crtn_self().

Une coroutine est définie par un nom et une fonction d'entrée qui reçoit un paramètre de type pointeur sur void et à l'issue de laquelle la coroutine se termine. Une coroutine peut aussi se terminer avant le terme de sa fonction d'entrée en appelant crtn_exit(). Une coroutine peut aussi être arrêtée par une autre avec un appel à crtn_cancel(). Une coroutine terminée reste dans un état zombie tant qu'une autre coroutine ne récupère pas son statut de fin avec crtn_join(). Le statut est un entier dont la signification est laissée au choix de l'utilisateur.

À la création des coroutines, il est possible de définir des attributs tels que la taille de pile. La fonction crtn_attr_new() alloue une structure de type crtn_attr_t pour les attributs. Ces derniers sont ensuite définis avec des fonctions spécifiques telles que crtn_set_attr_stack_size() pour définir la taille de pile. La structure est désallouée par crtn_attr_delete().

Une coroutine rend la main explicitement en appelant crtn_yield(). Ce service reçoit l'adresse d'un pointeur en paramètre pour passer des données à une coroutine qui se mettrait en attente sur elle via crtn_wait().

Si un service de la librairie échoue, le service crtn_errno() retourne le code d'erreur associé.

1.2 La librairie

La librairie est sous licence LGPL [2]. Elle est construite avec cmake [3]. La version qui sert de support à cet article est la 0.2.0. L'arborescence du code source a quatre sous-répertoires :

• lib : code source de la librairie ;
• include : fichier d'entête de l'API ;
• man : manuels de l'API ;
• tests : suite de tests de l'API.

La configuration, la génération et l'installation (par défaut dans /usr/local) de la librairie se fait à partir de la racine des sources (sous-répertoire crtn) :

Les programmes d'exemple cités dans la suite de l'article se trouvent dans le sous-répertoire tests des sources.

Après installation, les manuels en ligne sont accessibles :

La librairie se désinstalle de la manière suivante :

1.3 Première utilisation

Le premier opus s'était achevé sur des programmes d'exemple de mise en œuvre de coroutines avec les primitives de la librairie C. Le programme switch_ctx2 alternait l'exécution de trois flux : main(), func1() et func2(). Les deux derniers étaient de type stackless. Voici une réécriture du programme avec les fonctions de haut niveau. Les fonctions de l'API sont mises en exergue :

À l'exécution (qu'on effectue à partir de la racine des sources de la librairie une fois générée), on passe bien d'un flux à l'autre à chaque appui sur la touche <Return> :

Bien entendu, on a reproduit la même erreur qu'avec le programme original. Étant donné que les coroutines sont de type stackless, elles partagent la même pile, l'adresse de leur variable locale se trouve donc au même endroit (0x557d036936e4) et par conséquent, la valeur prise (2) est celle positionnée par func2, car elle a fait son initialisation après func1. On notera que le programme principal est considéré comme une coroutine stackful par la librairie CRTN. Sa pile est celle du programme principal. Il ne perturbe donc pas la pile des autres coroutines.

Le même programme avec des coroutines de type stackful fonctionne correctement, car il y a une pile dédiée à chaque coroutine. Pour cela, il suffit de modifier les attributs des coroutines comme on le fait dans le fichier tests/switch_ctx3.c :

L'exécution montre que les variables value1 et value2 n'étant plus à la même adresse (respectivement 0x55a8fb24fe14 et 0x55a8fb253e24), l'affichage est cohérent :

2. Le fonctionnement interne de la librairie

Nous n'allons pas passer en revue une à une toutes les lignes du code source de la librairie, mais plutôt nous concentrer sur les structures de données et fonctionnalités principales. L'essentiel du code source des fonctions de l'API est localisé dans le fichier lib/crtn.c.

2.1 Création d'une coroutine

Une coroutine est créée avec le service crtn_spawn() :

Le service reçoit en paramètres :

• un pointeur sur un identifiant unique : le Coroutine IDentifier (cid). En interne, c'est un entier, mais le type exposé est crtn_t ;
• un nom d'une longueur maximale de CRTN_NAME_SZ caractères (caractère '\0' de fin de chaîne compris !) ;
• la fonction d'entrée entry ainsi que l'adresse param d'un paramètre quelconque passé à cette dernière. La fonction retourne un entier (le statut de terminaison) dont la signification est laissée au choix de l'utilisateur ;
• des attributs définissant des propriétés particulières. On les verra par la suite.

Au retour de cette fonction, la coroutine est en attente de démarrage.

Un espace mémoire est associé à la coroutine afin d'y stocker les valeurs des registres du processeur ainsi que l'état de la pile au moment de la dernière suspension de la coroutine. Ils sont restaurés lorsque la coroutine reprend la main. Par analogie avec les appellations couramment utilisées dans les systèmes d'exploitation où un descripteur de tâche est nommé Task Control Block, nous utilisons l'expression Coroutine Control Block (CCB). Cet espace contient aussi d'autres informations privées comme l'identifiant unique, le nom, l'adresse du point d'entrée ou encore l'état courant de la coroutine. C'est une structure interne au service nommée crtn_ccb_t, non visible par l'utilisateur et définie dans lib/crtn_ccb.h :

Le CCB de la coroutine en cours d'exécution est pointé par la variable globale :

C'est l'équivalent du pointeur this référençant l'objet courant en C++ ou le pointeur current référençant la tâche en cours d'exécution dans le noyau Linux.

Le champ ctx contient la sauvegarde des registres et du masque de signaux. Il est renseigné par les services getcontext() et makecontext() que nous avons étudiés dans le précédent article [1].

makecontext() permet de définir la pile d'exécution ainsi que le point d'entrée de la coroutine. Pour ce dernier, la librairie utilise la fonction interne crtn_entry() qui appelle le point d'entrée avec son paramètre spécifié par crtn_spawn() (champs entry et param), puis appelle la fonction interne crtn_end() pour gérer la terminaison de la coroutine :

2.2 La pile

Il y a deux familles de coroutines : celles qui ont une pile (stackful) et celles qui n'en ont pas (stackless). Pour les premières, nous faisons le choix de stocker le CCB à la base de la pile tandis que pour les secondes, le CCB est un espace mémoire indépendant comme indiqué en figure 2.

Quand le CCB est dans l'espace mémoire de la pile, il se trouve donc en fin d'espace mémoire. Sur certaines architectures, les contraintes d'alignement font qu'il y a un padding éventuel entre la fin du CCB et la fin de l'espace mémoire de la pile. Le code suivant de crtn_spawn() réalise cela de manière portable avec l'opérateur __alignof()__ :

L'adresse de départ du CCB est aussi celle de la pile qui croît dans l'autre sens (vers les adresses basses).

Une coroutine stackless a en réalité quand même besoin d'une pile pour manipuler des variables locales et appeler des fonctions. Mais la pile est globale et partagée avec les autres coroutines stackless. Il s'agit de la variable globale :

L'intérêt de ces coroutines est d'économiser de la mémoire. Mais il faut garder à l'esprit que la pile est altérée (clobbered stack) lorsqu'une coroutine de ce type prend la main, étant donné que ses stack frames était utilisées par toute coroutine stackless active juste avant elle. Les données en pile des coroutines stackless sont donc éphémères. Les limitations sont les suivantes :

1. Les variables locales sont considérées comme invalides lorsque la coroutine stackless reprend la main.
2. Une coroutine stackless ne doit pas céder la main lorsqu'elle est dans une sous-fonction (par rapport à son point d'entrée), car les données d'appel et l'adresse de retour dans l'appelant risquent d'être altérées.

La taille par défaut de la pile partagée est :

Dans la suite, nous verrons que le service crtn_cancel() peut être amené à installer un contexte en pile pour arrêter la coroutine cible. Afin d'éviter l'altération de ce contexte dans le cas des coroutines stackless, le CCB est installé dans un espace avec une pile de taille minimale dédiée à l'opération cancel. D'où la pile au-dessus du CCB de la coroutine stackless sur la figure 2.

Le champ stack du CCB pointe sur l'espace alloué à la pile.

2.3 Les attributs

Les attributs d'une coroutine sont réunis dans une structure crtn_attr_t allouée par crtn_attr_new() :

La structure est opaque pour l'utilisateur. Les propriétés sont positionnées avec des services dédiés :

• crtn_set_attr_type() positionne le type d'ordonnancement (stepper ou par défaut standalone) et spécifie si la coroutine a une pile (stackless ou par défaut stackful) ;
• crtn_set_attr_stack_size() positionne la taille de la pile (lorsque la coroutine est de type stackful). La taille par défaut est CRTN_DEFAULT_STACK_SIZE.

La structure ainsi renseignée est passée en dernier paramètre à crtn_spawn(). Ce sont les valeurs par défaut qui s'appliquent si le paramètre est NULL.

La structure est désallouée avec :

2.4 L'ordonnancement

On distingue deux types de fonctionnements pour une coroutine :

• Le mode pas-à-pas (stepper) fait qu'une coroutine reste suspendue tant qu'une autre ne se met pas en attente sur elle via crtn_wait() ;
• Le mode autonome (standalone) fait qu'une coroutine est toujours prête à reprendre son exécution.

Contrairement aux threads et processus, le système d'exploitation n'a aucune idée de l'existence des coroutines et n'intervient donc pas dans leur ordonnancement (scheduling). L'ordre d'exécution est coopératif dans la mesure où la décision de rendre le processeur est effectuée par l'appel explicite au service :

Cette fonction réalise l'opération de commutation de contexte (context switch) en suspendant l'exécution de la coroutine appelante et en reprenant l'exécution (resume) d'une autre. Cela est réalisé en appelant swapcontext() [1] qui sauvegarde/restaure l'état des registres et de la pile stockés dans les CCB.

D'autres services comme crtn_wait() ou crtn_join(), vus plus loin, suspendent aussi la coroutine appelante au profit des coroutines ciblées : dans ces cas, crtn_yield() est implicitement appelée.

L'algorithme d'ordonnancement s'appuie sur une liste de coroutines prêtes pour l'exécution (runnable list) :

Le chaînage dans la liste est effectué avec le champ link du CCB. La liste est gérée de manière FIFO avec les règles suivantes pour minimiser les risques de famine provoqués par des coroutines reprenant la main continuellement au détriment d'autres :

• la prochaine coroutine à exécuter est en tête de liste ;
• une coroutine nouvellement créée est chaînée en queue de liste si elle est de type standalone ;
• une coroutine stepper est mise en queue de liste lorsqu'elle est activée avec crtn_wait() ;
• une coroutine cédant la main est chaînée en queue de liste si elle est de type standalone.

Voici l'extrait de code de l'ordonnanceur qui gère les coroutines standalone :

Une coroutine stepper reprend son exécution à l'initiative d'une autre coroutine via l'appel à :

Au moment de céder la main, la coroutine stepper peut passer des données à la coroutine en attente sur elle via le pointeur passé en paramètre de crtn_yield(). La coroutine en attente les récupère via le second paramètre de crtn_wait(). Voici le code source de la partie de l'ordonnanceur concernant les coroutines stepper :

2.5 Diagramme d'état

Pendant sa durée de vie, une coroutine passe par différents états, conformément au diagramme de la figure 3. L'état courant d'une coroutine est stocké dans le champ state du CCB.

Une coroutine prend vie suite à un appel à ctrn_spawn(). Son état passe de allocated à runnable (si son ordonnancement est standalone) ou ready (si son ordonnancement est stepper).

La coroutine en cours d'exécution est dans l'état running. Une seule coroutine est dans cet état à tout moment durant l'exécution du programme. La première à être dans cet état est la coroutine Main.

Sur appel à crtn_yield(), une coroutine passe de running à ready (si elle est de type stepper) ou runnable (si elle est de type standalone).

Une coroutine passe à l'état waiting sur appel à ctrn_wait() ou crtn_join(). Elle reste dans cet état le temps que la coroutine cible appelle crtn_yield() ou se termine.

Une coroutine passe dans l'état zombie lorsque son point d'entrée arrive à terme, lorsqu'elle appelle crtn_exit() ou qu'une coroutine a appelé crtn_cancel() avec son cid en paramètre.

Sur un appel à crtn_cancel(), la coroutine cible passe dans l'état runnable si elle n'y était pas déjà afin de déclencher sa terminaison.

2.6 Terminaison

Une coroutine se termine avec un statut de terminaison :

• à l'issue de sa fonction d'entrée qui retourne le statut de terminaison comme valeur de retour ;
• avant la fin de son point d'entrée en appelant le service crtn_exit() auquel le statut de terminaison est passé en paramètre ;
• lorsqu'une autre coroutine appelle crtn_cancel() avec son cid. Le statut de terminaison est alors positionné à la valeur réservée CRTN_STATUS_CANCELLED.

Une fois terminée, une coroutine passe dans l'état zombie jusqu'à un appel à crtn_join() par une autre coroutine afin de libérer ses structures de données (CCB et pile) et récupérer le statut de terminaison.

Si au moment de l'appel à crtn_cancel(), la coroutine cible n'est pas dans l'état zombie, le service crée une stack frame sur sa pile à l'aide du service makecontext() afin de provoquer l'appel à la fonction de terminaison interne crtn_end(). Dans le cas des coroutines stackless, la stack frame est installée sur la pile dédiée au cancel spécifique à la coroutine pour éviter toute altération par une autre coroutine stackless qui partage la même pile. Un changement de pile est donc opéré (cf. la pile au-dessus du CCB des coroutines stackless sur la figure 2).

2.7 Synchronisation

En appelant crtn_wait(), une coroutine suspend son exécution au profit d'une coroutine cible de type stepper. L'état de la coroutine cible est changé en runnable, l'adresse du CCB de la coroutine en attente est mémorisée dans le champ waiting du CCB de la cible et la coroutine appelante est mise dans l'état waiting. Ainsi, lorsque la coroutine cible se suspend en appelant crtn_yield(), elle met à jour le pointeur yielded_data de son CCB avec le paramètre passé à crtn_yield(), elle repasse dans l'état ready et la coroutine dont le CCB est pointé par le champ waiting est remise dans l'état runnable. Cette dernière peut récupérer les données de la cible via le champ yielded_data du CCB de la cible :

Si la coroutine cible n’est pas passée dans l'état zombie, alors le code de retour du service est CRTN_DEAD pour signifier la terminaison.

En appelant crtn_join(), une coroutine attend la terminaison d'une coroutine cible pour récupérer son statut de terminaison et libérer ses structures de données (CCB et pile) :

• si la coroutine cible est terminée (état zombie), le statut de terminaison est disponible, le CCB de la coroutine cible est libéré ;
• si la coroutine cible est runnable, ready ou waiting (car elle serait dans un appel à crtn_wait() ou crtn_join() par exemple), l'appelant est mis dans l'état waiting et l'adresse de son CCB est mémorisée dans le champ joining du CCB de la cible. Cette dernière réveillera la coroutine appelante lorsqu'elle se terminera.

S'il n'est pas nul, le statut de fin de la coroutine est stocké à l'adresse indiquée par le paramètre status.

2.8 Gestion des erreurs

Les services de la librairie peuvent retourner des erreurs. Le code d'erreur résulte de contrôles internes à la librairie (p. ex. erreur sur les paramètres passés à la fonction), mais aussi d'appels système effectués par les fonctions de la glibc sous-jacente (par exemple, appel à rt_sigprocmask() par les fonctions get/make/swapcontext()). En conséquence, la librairie met à disposition un code d'erreur global sur le même modèle que le mécanisme errno de la librairie C où, dans les environnements multithread, errno est une variable spécifique à chaque thread pour des raisons de réentrance. Elle est en fait une macro appelant une fonction qui récupère le code d'erreur stocké dans les données spécifiques du thread en cours d'exécution. Pour les mêmes raisons de réentrance, le code d'erreur de CRTN est aussi spécifique à chaque coroutine. Il est stocké dans le champ err_num du CCB et est accessible sur retour erreur d'un service via :

Les codes d'erreur sont dans le fichier d'entête <errno.h> de la glibc.

2.9 Initialisation

À l'initialisation de la librairie, le programme principal (main thread) se voit allouer un contexte de coroutine avec le nom Main et les attributs par défaut, sauf pour la pile, qui reste celle du processus :

C'est la première coroutine à être dans l'état running. Son cid est égal à 0 :

3. Applications

Dans son encyclopédie de l'algorithmique [4], afin de justifier l'utilisation du principe des coroutines, D. Knuth [5] propose une vision de la programmation dénuée de la notion d'appelant et d'appelé au profit d'entités coopérant sur un pied d'égalité. Souvent (mais pas toujours !) efficaces, les coroutines peuvent aussi simplifier l'écriture des programmes et réduire leur complexité. Les domaines d'application sont nombreux. Nous présentons ici quelques cas à travers deux programmes simples.

3.1 Un générateur

L'exemple dans tests/fibonacci.c implémente la suite de Fibonacci [6] sous forme d'une coroutine de type stepper générant le terme suivant à chaque activation.

Après avoir créé la coroutine Fibonacci, générateur des termes de la suite, la fonction main() appelle crtn_wait() toutes les secondes pour récupérer le terme suivant. Fibonacci retourne d'abord les deux premiers termes aux deux premières activations, puis entre dans une boucle pour retourner les termes suivants via crtn_yield(). La figure 4 illustre le propos.

Le code source est le suivant :

À l'exécution, le terme suivant de la suite est affiché toutes les secondes :

Pour faire l'équivalent en programmation traditionnelle, la fonction fibonacci() serait l'appelée et devrait définir ses variables internes (prevn_1 et prevn) en statique pour les rendre persistantes d'un appel à l'autre et retourner la valeur du terme courant en code de retour. La fonction main() quant à elle serait l'appelant et déclencherait la fonction fibonacci() toutes les secondes.

Plus généralement, une coroutine peut implémenter un itérateur parcourant (éventuellement de manière récursive) une liste ou un arbre d'éléments quelconques. À chaque activation, la coroutine retourne les informations relatives au jalon suivant dans le parcours.

3.2 Un modèle producteur/consommateur

Les coroutines s'appliquent aussi au modèle producteur/consommateur où une entité produit des informations exploitées par l'autre au fil de l'eau à la manière d'une communication par tube (pipe) Linux. Elles trouvent aussi leur intérêt dans l'implémentation des moteurs d'automate qui reçoivent en entrée un événement provoquant une action et une transition dans un état suivant. Les programmes basés sur une boucle d’événements sont aussi des utilisateurs potentiels du concept de coroutine.

Nous illustrons cela avec le programme tests/wc4.c reproduisant la commande wc du shell Linux qui compte les caractères, les mots et les lignes arrivant sur son entrée standard. La figure 5 montre l'automate de l'algorithme.

La figure 6 schématise la mise en œuvre du programme :

• une boucle d’événements permet de réceptionner les caractères arrivant sur l'entrée standard ;
• les caractères sont lus par la coroutine Main et placés dans un buffer qui fait office de tube. Dès que des données sont mises dans le tube, la coroutine Counter est activée ;
• à l'autre bout du tube, la coroutine Counter lit les caractères, les soumet à l'automate et réactive la coroutine Main lorsque le tube est vide.

La boucle d’événements effectue une lecture non bloquante sur l'entrée standard avec la fonction nb_read(). Cette dernière utilise select() pour n'effectuer un polling toutes les 5 millisecondes qu'à la condition où il n'y aurait pas de données disponibles. Sinon, elle rend la main dès qu'elle a lu des données en entrée. La fin de fichier (retour de read() égal à 0) est aussi mise dans le buffer (EOF).

La coroutine Main, premier flux d'exécution, crée la coroutine Counter, second flux d'exécution, puis appelle simplement la fonction fill_buffer() pour remplir le buffer global de taille BUFFER_SIZE. À chaque retour de nb_read() qui indique que des données sont mises dans le buffer, la seconde coroutine est activée. Main se termine lorsque fill_buffer() se termine :

Counter met en œuvre l'automate de la figure 5 et se contente d'appeler read_buffer() pour lire les caractères dans le tube. Cette dernière suspend la coroutine Counter au profit de la coroutine Main à chaque fois que le pointeur de lecture arrive en fin de buffer :

Nous avons ainsi deux flux d'exécution simples : le premier remplit le buffer jusqu'à ce qu'il rencontre EOF et le second lit le buffer, met en œuvre l'automate de comptage et s'arrête quand il lit EOF. Chaque coroutine vit donc sa vie : l'une pour remplir le tube et l'autre pour le vider. Elles coopèrent implicitement. Il n'y a pas de notion d'appelant et d'appelé. À l'exécution, nous obtenons :

Le répertoire tests contient différentes versions de wc écrites avec des coroutines.

Conclusion

La librairie CRTN s'ajoute, sans prétention, à une longue liste d'implémentations des coroutines disponibles en open source sur Internet. Le prétexte de cet article était plutôt d'expliquer les principes qui régissent le concept et les domaines d'application que de véritablement proposer une nouvelle API de référence. Le but était avant tout pédagogique pour aider à appréhender les implémentations natives dans les langages de haut niveau comme Python, Kotlin, C++, etc.

Le lecteur pourra adapter cette librairie aux contraintes d'un environnement professionnel avec les fonctionnalités supplémentaires suivantes :

• sécurisation des piles pour détecter les débordements en utilisant mmap() et une page de protection en bout de pile avec mprotect() ;
• gestion des signaux Linux sur une pile séparée avec sigaltstack() pour ne pas déclencher les handlers sur la pile de la coroutine en cours d'exécution afin de limiter les risques de débordement de pile ;
• ajout de services de communication inter-coroutine comme les mailbox pour envoyer des messages d'une coroutine à l'autre. D'ailleurs, le sous-répertoire lib des sources propose un tel service ;
• optimisation des performances en supprimant l'appel système rt_sigprocmask() réalisé par les fonctions sous-jacentes get/make/swapcontext().

Références

[1] R. KOUCHA, « Exécution concurrente avec les coroutines », GNU/Linux magazine n°251 : https://connect.ed-diamond.com/gnu-linux-magazine/glmf-251/execution-concurrente-avec-les-coroutines

[2] La licence LGPL : https://fr.wikipedia.org/wiki/Licence_publique_g%C3%A9n%C3%A9rale_limit%C3%A9e_GNU

[3] cmake : https://fr.wikipedia.org/wiki/CMake

[4] The art of computer programming : https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

[5] Donald Knuth : https://fr.wikipedia.org/wiki/Donald_Knuth

[6] Suite de Fibonacci : https://fr.wikipedia.org/wiki/Suite_de_Fibonacci