Une API de coroutines pour le langage C

Magazine
Marque
GNU/Linux Magazine
Numéro
253
Mois de parution
novembre 2021
Spécialité(s)


Résumé

Contrairement à d'autres langages comme Go, C++ ou Python, le langage C ne supporte pas les coroutines en natif, malgré leur retour sous les projecteurs pour répondre aux besoins de l'embarqué et de l'IoT. Grâce à la librairie C, il est possible d'écrire une API qui les propose.


Body

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.

Les exemples présentés se trouvent sur https://github.com/Rachid-Koucha/crtn.git. Après clonage, les fichiers d'exemples se trouvent dans le sous-répertoire tests des sources de la librairie CRTN.

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.

figure 01 layers-s 0

Fig. 1 : L'architecture en couche de la librairie CRTN.

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

$ git clone https://github.com/Rachid-Koucha/crtn.git    # Clonage
Cloning into 'crtn'...
[...]
$ cd crtn
crtn$ git checkout tags/v0.2.0    # Clonage de l'étiquette v0.2.0
crtn$ cmake .        # Configuration
-- The C compiler identification is GNU ...
-- Check for working C compiler: /usr/bin/cc
[...]
crtn$ make        # Génération
[ 4%] Building C object lib/CMakeFiles/crtn.dir/crtn.c.o
[ 8%] Building C object lib/CMakeFiles/crtn.dir/crtn_mbx.c.o
[ 12%] Building C object lib/CMakeFiles/crtn.dir/crtn_sem.c.o
[ 16%] Linking C shared library libcrtn.so
[...]
crtn$ sudo make install    # Installation
[...]
-- Install configuration: ""
-- Installing: /usr/local/include/crtn.h
-- Installing: /usr/local/lib/libcrtn.so.0.2.0
-- Installing: /usr/local/lib/libcrtn.so.0
-- Installing: /usr/local/lib/libcrtn.so
[...]

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 :

crtn$ man crtn_spawn
CRTN(3)                           API v0.2.0                           CRTN(3)
 
NAME
       crtn - API of CoRouTiNe service
 
SYNOPSIS
       #include <crtn.h>
 
       typedef int (* crtn_entry_t)(void *param);
 
       int crtn_spawn(crtn_t *cid, const char *name, crtn_entry_t entry,
            void *param, crtn_attr_t attr);
[...]
DESCRIPTION
       The CRTN API is a set of services to manage coroutines.
 
       The crtn_spawn() function spawns a new coroutine. It is passed a string
       of at most CRTN_NAME_SZ (24) characters including the terminating NULL
       in name, the entry point function along with its parameter pointed by
       param and the attributes pointed by attr. If the latter is NULL, the
[...]

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

crtn$ sudo make uninstall
Scanning dependencies of target uninstall
-- Uninstalling /usr/local/include/crtn.h
-- Uninstalling /usr/local/lib/libcrtn.so.0.2.0
[...]

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 :

#include <stdio.h>
#include "crtn.h"
 
int func1(void *param)
{
  int value1 = 1;
[...]
  while(1) {
    printf("func1 is running, value1@%p = %d\n", &value1, value1);
    crtn_yield(0);
  }
}
 
int func2(void *param)
{
  int value2 = 2;
[...]
  while(1) {
    printf("func2 is running, value2@%p = %d\n", &value2, value2);
    crtn_yield(0);
  }
}
 
int main(void)
{
  int c = 0;
  crtn_t cid1, cid2;
  crtn_attr_t attr;
 
  attr = crtn_attr_new();
  crtn_set_attr_type(attr, CRTN_TYPE_STEPPER|CRTN_TYPE_STACKLESS);
 
  crtn_spawn(&cid1, "func1", func1, 0, attr);
  crtn_spawn(&cid2, "func2", func2, 0, attr);
 
  crtn_attr_delete(attr);
 
  while(1) {
    if (getchar() == EOF) {
      printf("Exiting\n");
      break;
    }
    c = (c + 1) % 2;
    if (1 == c) {
      crtn_wait(cid1, 0);
    } else {
      crtn_wait(cid2, 0);
    }
  }
 
  crtn_cancel(cid1);
  crtn_cancel(cid2);
 
  crtn_join(cid1, 0);
  crtn_join(cid2, 0);
 
  return 0;
}

À 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> :

$ tests/switch_ctx2
<RETURN>
func1 is running, value1@0x557d036936e4 = 1
<RETURN>
func2 is running, value2@0x557d036936e4 = 2
<RETURN>
func1 is running, value1@0x557d036936e4 = 2
<RETURN>
func2 is running, value2@0x557d036936e4 = 2
<CTRL+D>
Exiting

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 :

crtn_set_attr_type(attr, CRTN_TYPE_STEPPER|CRTN_TYPE_STACKFUL);

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 :

$ tests/switch_ctx3
<RETURN>
func1 is running, value1@0x55a8fb24fe14 = 1
<RETURN>
func2 is running, value2@0x55a8fb253e24 = 2
<RETURN>
func1 is running, value1@0x55a8fb24fe14 = 1
<RETURN>
func2 is running, value2@0x55a8fb253e24 = 2
<CTRL+D>
Exiting

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() :

typedef int crtn_t;#define CRTN_NAME_SZ 24typedef int (* crtn_entry_t)(void *param);
extern int crtn_spawn(crtn_t *cid, const char *name, crtn_entry_t entry, void *param, crtn_attr_t attr);

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 :

typedef struct crtn_ccb
{
  int cid;
 
  int state;
#define CRTN_STATE_ALLOCATED 0
#define CRTN_STATE_READY      1
#define CRTN_STATE_RUNNABLE   2
#define CRTN_STATE_RUNNING    3
#define CRTN_STATE_WAITING    4
#define CRTN_STATE_ZOMBIE     5
 
  crtn_ccb_attr_t attr;
 
  // Entry point (function, parameter and return code)
  crtn_entry_t entry;
  void         *param;
  int           status;
 
  char *stack;
 
  // Saved registers and signal mask
  ucontext_t ctx;
 
  // Error on last library/system call
  int err_num;
 
  // Link into the current list
  crtn_link_t link;
 
  // Joining corouting
  struct crtn_ccb *joining;
[...]
  // Waiting corouting
  struct crtn_ccb *waiting;
[...]
  void *yielded_data;
 
  char name[CRTN_NAME_SZ];
[...]
} crtn_ccb_t;

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

crtn_ccb_t *crtn_current;

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 :

static void crtn_entry(void)
{
  crtn_ccb_t *ccb = crtn_current;
  int status;
 
  // Call the entry point
  status = ccb->entry(ccb->param);
 
  // Handle termination (cancellation, exit)
  crtn_end(status);
}

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.

figure 02 ccb-s

Fig. 2 : Le CCB.

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()__ :

    // The CCB is aligned at the bottom of the stack
    p = stack + stack_sz - sizeof(crtn_ccb_t);
    p = (char *)((unsigned long)p & ~(__alignof__(crtn_ccb_t) - 1));
    ccb = (crtn_ccb_t *)p;
    stack_sz = (size_t)(p - stack);

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 :

static char *crtn_stackless;

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 :

#define CRTN_DEFAULT_STACK_SIZE (16 * 1024)

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() :

typedef void *crtn_attr_t;
extern crtn_attr_t crtn_attr_new(void);

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.
#define CRTN_TYPE_STANDALONE  0 // Default
#define CRTN_TYPE_STEPPER     1
 
#define CRTN_TYPE_STACKFUL    0 // Default
#define CRTN_TYPE_STACKLESS   2
extern int crtn_set_attr_type(crtn_attr_t attr, unsigned int type);
 
extern int crtn_set_attr_stack_size(crtn_attr_t attr, size_t 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 :

extern int crtn_attr_delete(crtn_attr_t attr);

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 :

extern int crtn_yield(void *data);

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

static crtn_link_t crtn_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 :

int crtn_yield(void *data)
{ int rc;
  crtn_link_t *plink;
  crtn_ccb_t *next_ccb;
  crtn_ccb_t *old_ccb;
[...]
        // Put the current CCB at the end of the runnable list if it is not
        // already the last. Brand new coroutines from calls to crtn_spawn()
        // may be located before the running coroutine in the runnable list.
        if (crtn_runnable_list.prev != &(crtn_current->link)) {
          CRTN_LIST_DEL(&(crtn_current->link));
          CRTN_LIST_ADD_TAIL(&crtn_runnable_list, &(crtn_current->link));
        }
 
        // Get the link of the schedulable coroutine (1st of the list)
        plink = CRTN_LIST_FRONT(&crtn_runnable_list);
 
        // The list can't be empty (otherwise it is an internal bug!)
        assert(plink);
 
        // Context switch if it is not the current one
        if (plink != &(crtn_current->link)) {
          crtn_current->state = CRTN_STATE_RUNNABLE;
          next_ccb = CRTN_LINK2CCB(plink);
          old_ccb = crtn_current;
          crtn_current = next_ccb;
          crtn_current->state = CRTN_STATE_RUNNING;
          swapcontext(&(old_ccb->ctx), &(next_ccb→ctx));          rc = CRTN_SCHED_OTHER;
        } else {
          rc = CRTN_SCHED_SELF;
        }
[...]

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

extern int crtn_wait(crtn_t cid, void **ret);

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 :

void crtn_yield(void *data)
{ int rc;
  crtn_link_t *plink;
  crtn_ccb_t *next_ccb;
  crtn_ccb_t *old_ccb;
[...]
      if (crtn_current->attr.type & CRTN_TYPE_STEPPER) {
 
        // If some coroutine is waiting on the current coroutine
        if (crtn_current->waiting) {
          // Pass the data
          crtn_current->yielded_data = data;
 
          // Put the waiting coroutine in the runnable list
          crtn_make_runnable(&(crtn_current->waiting->link));
        }
 
        // Put current coroutine in the READY state
        CRTN_LIST_DEL(&(crtn_current->link));
        crtn_current->state = CRTN_STATE_READY;
 
        // Get the link of the schedulable coroutine
        plink = CRTN_LIST_FRONT(&crtn_runnable_list);
 
        // If there no schedulable coroutines, this is a dead end!
        assert(plink);
 
        // Context switch
        next_ccb = CRTN_LINK2CCB(plink);
        old_ccb = crtn_current;
        crtn_current = next_ccb;
        crtn_current->state = CRTN_STATE_RUNNING;
        swapcontext(&(old_ccb->ctx), &(next_ccb→ctx));
        rc = CRTN_SCHED_OTHER;[...]

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.

figure 03 state diagram-s

Fig. 3 : Diagramme d'état d'une coroutine.

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

int crtn_cancel(crtn_t cid)
{
crtn_ccb_t *ccb, *ccb1;
[...]
  switch(ccb->state) {
[...]
    case CRTN_STATE_WAITING: {
 
      // The target coroutine is waiting on some resource      // ==> Disable the wait
      if (ccb->waiting_on) {
        ccb1 = ccb->waiting_on;
        ccb1->waiting = 0;
        ccb->waiting_on = 0;
      } else if (ccb->joining_on) {
        ccb1 = ccb->joining_on;
        ccb1->joining = 0;
        ccb->joining_on = 0;
      }
 
      // Unlink the coroutine from the list of the object
      // it is waiting on (e.g. semaphore, mailbox)
      // If it is not linked, the macro does not change the links
      CRTN_LIST_DEL(&(ccb->link));
    }
    __CRTN_FALLTHROUGH
 
    case CRTN_STATE_READY: {
      // Put the target coroutine at the beginning of
      // the runnable queue and change its state to runnable
      crtn_make_runnable(&(ccb->link));
    }
    break;
 
    default: {
      // The target coroutine is in runnable state
      assert(ccb->state == CRTN_STATE_RUNNABLE);
    }
    break;
 
  } // End switch
 
  ccb->flags |= CRTN_CCB_FLAG_CANCELLED;
 
  // Change the context of the target coroutine to make it call the
  // termination routine
  if (ccb->attr.type & CRTN_TYPE_STACKLESS) {
    // For stackless coroutines, we use the dedicated cancel stack otherwise
    // the stack frame could be clobbered
    ccb->ctx.uc_stack.ss_sp = ccb->cancel_stack;
    ccb->ctx.uc_stack.ss_size = ccb->cancel_stack_size;
    ccb->ctx.uc_stack.ss_flags = 0;
 
    makecontext(&(ccb->ctx), (mkctx_func_t)crtn_end, 1, CRTN_STATUS_CANCELLED);
  } else {
    makecontext(&(ccb->ctx), (mkctx_func_t)crtn_end, 1, CRTN_STATUS_CANCELLED);
  }
  return 0;
}

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 :

int crtn_wait(crtn_t cid, void **ret)
{
[...]
  crtn_make_runnable(&(ccb->link));
 
  crtn_make_waiting(0, &(crtn_current->link));
 
  ccb->waiting = crtn_current;
  crtn_current->waiting_on = ccb;
 
  // Give back the processor
  crtn_yield(0);
 
  // For stackless coroutines, the local variables are clobbered here
  // ==> Reload 'ccb'
  ccb = crtn_current->waiting_on;
 
  ccb->waiting = 0;
  crtn_current->waiting_on = 0;
 
  if (ret) {
    *ret = ccb->yielded_data;
  }
 
  // If the call to crtn_wait() trigger the termination of the target
  // coroutine or if it has been cancelled
  if (ccb->state != CRTN_STATE_READY) {
    assert(ccb->state == CRTN_STATE_ZOMBIE);
    return CRTN_DEAD;
  }
  return 0;
}

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.
int crtn_join(crtn_t cid, int *status)
{
[...]
  switch(ccb->state) {
 
    case CRTN_STATE_ZOMBIE: {
      ccb->joining = crtn_current;
      crtn_current->joining_on = ccb;
    }
    break;
 
    case CRTN_STATE_RUNNABLE:
    case CRTN_STATE_WAITING:
    case CRTN_STATE_READY: {
 
      crtn_make_waiting(0, &(crtn_current->link));
 
      ccb->joining = crtn_current;
      crtn_current->joining_on = ccb;
 
      // Give back the processor
      crtn_yield(0);
    }
    break;
[...] } // End switch
 
  // For stackless coroutines, the local variables are clobbered here
  // ==> Reload 'ccb'
  ccb = crtn_current->joining_on;
 
  if (status) {
    *status = ccb->status;
  }
 
  crtn_current->joining_on = 0;
  ccb->joining = 0;
 
  // Free the coroutine
  crtn_free(ccb);
  return 0;
}

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 :

extern int crtn_errno(void);

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 :

void __attribute__ ((constructor)) crtn_lib_init(void);
 
void crtn_lib_init(void)
{
  crtn_ccb_t *ccb;
 
  // Initialize the list
  CRTN_LIST_INIT(&crtn_runnable_list);
 
  // Make the CCB of the main thread, no entry point
  ccb = crtn_current = &crtn_ccb_main;
  ccb->cid = crtn_get_id(ccb);
  assert(ccb->cid == CRTN_CID_MAIN);
  crtn_fill_ccb(ccb, "Main", 0, 0, 0, 0, 0);
 
  // Put the MAIN coroutine in the runnable list
  crtn_make_runnable(&(ccb->link));
 
  // Main is the first running coroutine
  ccb->state = CRTN_STATE_RUNNING;
}

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

#define CRTN_CID_MAIN   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.

figure 04 fibonacci-s

Fig. 4 : Les coroutines du programme Fibonacci.

Le code source est le suivant :

[...]
static int fibonacci(void *param)
{
  unsigned long long prevn_1;
  unsigned long long prevn;
  unsigned long long cur;
[...]
  cur = prevn_1 = 0;
  crtn_yield(&cur);
 
  cur = prevn = 1;
  crtn_yield(&cur);
 
  while (1) {[...]
    cur = prevn + prevn_1;
    crtn_yield(&cur);
    prevn_1 = prevn;
    prevn = cur;
  }
 
  return 0;
}
 
int main(void)
{
  crtn_t cid;
  int rc;
  int status;
  unsigned long long *seq;
  crtn_attr_t attr;
  unsigned int i;
[...] attr = crtn_attr_new();
[...]
  rc = crtn_set_attr_type(attr, CRTN_TYPE_STEPPER);
[...]
  rc = crtn_spawn(&cid, "Fibonacci", fibonacci, 0, attr);
[...]
  rc = crtn_attr_delete(attr);
[...]
  i = 0;
  while(1) {
    rc = crtn_wait(cid, (void **)&seq);
[...]
    printf("seq[%u]=%llu\n", i, *seq);
    i ++;
    sleep(1);
 
[...]
  } // End while
 
  rc = crtn_cancel(cid);
[...]
  rc = crtn_join(cid, &status);
[...]
  return status;
}

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

$ tests/fibonacci
seq[0]=0
seq[1]=1
seq[2]=1
seq[3]=2
[...]
seq[14]=377
seq[15]=610
seq[16]=987
seq[17]=1597
seq[18]=2584
<CTRL+C>
Signal 2...

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.

figure 05 wc fsm-s

Fig. 5 : Automate du programme wc.

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.

figure 06 wc-s

Fig. 6 : Fonctionnement interne du programme wc.

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

int nb_read(int fd, char *buf, size_t bufsz)
{
int             rc;
fd_set          fdset;
int             nfds = fd + 1;
struct timeval to;
 
  to.tv_sec = 0;
  to.tv_usec = 0;
 
  while(1) {
    FD_ZERO(&fdset);
    FD_SET(fd, &fdset);
 
    rc = select(nfds, &fdset, NULL, NULL, &to);
    switch (rc) {
[...]
      // Timeout
      case 0: {
        // No data ==> Retry with a timeout 5 ms
        to.tv_usec = 5000;
      }
      break;
 
      // Incoming data
      default : {
        rc = read(fd, buf, bufsz);
[...]
        if (0 == rc) {
          buf[0] = EOF;
          return 1;
        }
 
        return rc;
      }
      break;
    }
  }
}

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 :

static int w_offset, r_offset;
 
#define BUFFER_SIZE 128
static char buffer[BUFFER_SIZE];
[...]
static void fill_buffer(void)
{
  do {
    w_offset = nb_read(0, buffer, BUFFER_SIZE);
 
    // If no error, there is at least an EOF in the buffer
    if (w_offset > 0) {
      crtn_yield(0);
    }
  } while (w_offset > 0 && buffer[w_offset-1] != EOF);
}
[...]
int main(void)
{
  crtn_t cid;
  int rc;
  int status;
 
  rc = crtn_spawn(&cid, "Counter", counter, 0, 0);
[...]
  fill_buffer();
 
  rc = crtn_join(cid, &status);
[...]
  printf("Lines: %zu / Words: %zu / Characters: %zu\n", cnts.nb_lines, cnts.nb_words, cnts.nb_chars);
 
  return status;
}

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 :

static int read_buffer(void)
{
  if (r_offset == w_offset) {
    crtn_yield(0);
    r_offset = 0;
  }
  cnts.nb_chars ++;
  return buffer[r_offset ++];
}
 
#define unread_buffer(c) do { \
                  assert(r_offset > 0); \
                  -- r_offset; \                  cnts.nb_chars --; \
                } while(0)
[...]
static void get_spaces(void)
{
  int c;
 
  c = read_buffer();
  while(isspace(c) && (c != '\n') && (c != EOF)) {
    c = read_buffer();
  }
 
  unread_buffer(c);
  return;
}
 
static void get_word(void)
{
  int c;
 
  cnts.nb_words ++;
 
  c = read_buffer();
  while(!isspace(c) && (c != EOF)) {
    c = read_buffer();
  }
 
  unread_buffer(c);
  return;
}
 
static void get_lines(void)
{
  int c;
 
  c = read_buffer();
  while(c == '\n') {
    cnts.nb_lines ++;
    c = read_buffer();
  }
 
  unread_buffer(c);
  return;
}
 
static int counter(void *param)
{
  int c;
[...]
  do {
 
    c = read_buffer();
    unread_buffer(c);
    if (c == '\n') {
      get_lines();
    } else if (isspace(c)) {
      get_spaces();
    } else if (c != EOF) {
      get_word();
    }
 
  } while (c != EOF);
 
  return 0;
}

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 :

$ cat /etc/passwd | tests/mywc4
Lines: 50 / Words: 91 / Characters: 3017
$ cat /etc/passwd | wc         
     50      91    3017

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



Article rédigé par

Par le(s) même(s) auteur(s)

Exécution concurrente avec les coroutines

Magazine
Marque
GNU/Linux Magazine
Numéro
251
Mois de parution
septembre 2021
Spécialité(s)
Résumé

Concept datant des premières heures de l'informatique, puis laissé en désuétude au profit des threads, les coroutines suscitent un engouement depuis quelques années, notamment dans le domaine de l'embarqué et de l'Internet of Things (IoT). Certains langages les supportent nativement. Le langage C ne les propose pas, mais la librairie C recèle des services qui permettent de les mettre en œuvre.

Les derniers articles Premiums

Les derniers articles Premium

Stubby : protection de votre vie privée via le chiffrement des requêtes DNS

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Depuis les révélations d’Edward Snowden sur l’espionnage de masse des communications sur Internet par la NSA, un effort massif a été fait pour protéger la vie en ligne des internautes. Cet effort s’est principalement concentré sur les outils de communication avec la généralisation de l’usage du chiffrement sur le web (désormais, plus de 90 % des échanges se font en HTTPS) et l’adoption en masse des messageries utilisant des protocoles de chiffrement de bout en bout. Cependant, toutes ces communications, bien que chiffrées, utilisent un protocole qui, lui, n’est pas chiffré par défaut, loin de là : le DNS. Voyons ensemble quels sont les risques que cela induit pour les internautes et comment nous pouvons améliorer la situation.

Surveillez la consommation énergétique de votre code

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Être en mesure de surveiller la consommation énergétique de nos applications est une idée attrayante, qui n'est que trop souvent mise à la marge aujourd'hui. C'est d'ailleurs paradoxal, quand on pense que de plus en plus de voitures permettent de connaître la consommation instantanée et la consommation moyenne du véhicule, mais que nos chers ordinateurs, fleurons de la technologie, ne le permettent pas pour nos applications... Mais c'est aussi une tendance qui s'affirme petit à petit et à laquelle à terme, il devrait être difficile d'échapper. Car même si ce n'est qu'un effet de bord, elle nous amène à créer des programmes plus efficaces, qui sont également moins chers à exécuter.

Donnez une autre dimension à vos logs avec Vector

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Avoir des informations précises et détaillées sur ce qu’il se passe dans une infrastructure, et sur les applications qu'elle héberge est un enjeu critique pour votre business. Cependant, ça demande du temps, temps qu'on préfère parfois se réserver pour d'autres tâches jugées plus prioritaires. Mais qu'un système plante, qu'une application perde les pédales ou qu'une faille de sécurité soit découverte et c'est la panique à bord ! Alors je vous le demande, qui voudrait rester aveugle quand l'observabilité a tout à vous offrir ?

Les listes de lecture

9 article(s) - ajoutée le 01/07/2020
Vous désirez apprendre le langage Python, mais ne savez pas trop par où commencer ? Cette liste de lecture vous permettra de faire vos premiers pas en découvrant l'écosystème de Python et en écrivant de petits scripts.
11 article(s) - ajoutée le 01/07/2020
La base de tout programme effectuant une tâche un tant soit peu complexe est un algorithme, une méthode permettant de manipuler des données pour obtenir un résultat attendu. Dans cette liste, vous pourrez découvrir quelques spécimens d'algorithmes.
10 article(s) - ajoutée le 01/07/2020
À quoi bon se targuer de posséder des pétaoctets de données si l'on est incapable d'analyser ces dernières ? Cette liste vous aidera à "faire parler" vos données.
Voir les 60 listes de lecture

Abonnez-vous maintenant

et profitez de tous les contenus en illimité

Je découvre les offres

Déjà abonné ? Connectez-vous