Exécution concurrente avec les coroutines

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.


Body

La notion de coroutine n'est pas nouvelle, car on attribue l'invention à Melvin Conway en 1958 [1]. Elles mettent en œuvre plusieurs flux d'exécution dans un programme. C'est un modèle efficace et léger antérieur à la notion de thread pour réaliser des activités concurrentes dans un programme. Contrairement au C, certains langages comme Go, Rust, Python ou C# les supportent en natif [2]. Le C++ les a aussi adoptées récemment [3]. En effet, dans le domaine de l'IoT et de l'embarqué, les coroutines reviennent sur le devant de la scène afin de répondre aux besoins d'efficacité dans des systèmes peu dotés en ressources matérielles. Elles permettent aussi de simplifier la programmation asynchrone pour traiter des événements [4].

Ce premier article décrit la mécanique de bas niveau et ébauche une mise en œuvre en langage C.

Les exemples présentés se trouvent sur http://www.rkoucha.fr/tech_corner/coroutines/coroutines.tgz.

C'est la version 2.31 du code source de la glibc qui est détaillée ci-après.

1. Flux d'exécution

1.1 Déroulement d'un programme

Le déroulement d'un programme consiste en un flux d'instructions contiguës en mémoire, exécutées l'une après l'autre par le processeur. Il s'appuie sur ses registres pour référencer ou stocker des données et effectuer des opérations. Le registre IP (Instruction Pointer) est toujours rechargé avec l'adresse de la prochaine instruction à exécuter. Certaines instructions provoquent des sauts (jump) pour exécuter non pas la suivante, mais une instruction située plus loin en mémoire et d'autres provoquent des appels de fonction (call) qui sont aussi des sauts, mais avec un retour (ret) à l'instruction située juste après le point d'appel. Une pile référencée par un registre BP (Base Pointer) stocke les paramètres passés à la fonction ainsi que ses variables locales et l'adresse de retour (stack frame). Sur quasiment toutes les architectures matérielles connues, la pile progresse des adresses hautes vers les adresses basses. L'adresse courante de son sommet est mémorisée dans le registre SP (Stack Pointer). La figure 1 schématise le principe.

figure 01 prog execution

Fig. 1 : Exécution d'un programme.

1.2 Exemple sur microprocesseur Intel

À titre d'illustration, dans le programme service, la fonction main() appelle la fonction service() avec huit paramètres. Cette dernière retourne un entier :

int service(int a, int b, int c, int d, char *str0, char *str1, char *str2, unsigned long ul)
{
int loc = c + 1;
 
  printf("%d %d %d %d %d %p %p %p %lu\n", a, b, c, loc, d, str0, str1, str2, ul);
 
  return 0;
}
 
int main(void)
{
  int rc = service(1, 2, 3, 4, "a", "b", "c", 1234567890);
  if (rc != 0) {
    printf("Erreur\n");
  }
 
  return 0;
}

Le fichier service.s contient le code assembleur du programme généré avec l'option -S de gcc :

$ gcc service.c -S
$ ls -l service.s
-rw-rw-r-- 1 rachid rachid 4505 janv.   6 13:45 service.s

Avant de plonger dans le détail des instructions, il faut préalablement connaître les conventions d'appel des fonctions en langage C. Comme nos exemples sont réalisés sur un PC équipé d'un processeur Intel 64 bits, nous les détaillons dans le cadre de l'architecture x86_64 [5] :

  1. Les six premiers paramètres de type entier ou pointeur passés à la fonction sont respectivement stockés dans les registres RDI, RSI, RDX, RCX, R8, R9 (pour les types flottants, des registres dédiés sont utilisés, mais on ne s'y attarde pas ici). Si la fonction reçoit plus de six paramètres, ils sont stockés en pile dans l'ordre inverse de leur apparition dans la liste des paramètres. On notera que la pile est toujours alignée sur un multiple de 16 octets. Le compilateur peut générer du padding pour respecter cet alignement.
  2. L'instruction call appelle la fonction. Elle stocke en pile l'adresse de la prochaine instruction à exécuter (c.-à-d. l'instruction qui suit l'appel à call, stockée dans le registre RIP).
  3. Dans la fonction appelée, les variables locales sont allouées dans la pile juste après l'adresse de retour dans l'appelant (le contenu du registre RSP est décrémenté pour réserver cette place).
  4. En fin de fonction, la valeur de retour est stockée dans le registre RAX et le pointeur de pile est incrémenté pour dépiler les variables locales (s'il y en a), de sorte que le sommet de la pile retourne au niveau de l'adresse de retour dans l'appelant. L'instruction ret dépile implicitement l'adresse de retour située au sommet de la pile et provoque un saut à l'emplacement mémoire correspondant.
  5. Le code appelant décrémente le pointeur de pile, de sorte à dépiler les paramètres qu'il a stockés (s'il y en avait plus de six).

Revenons au code assembleur de notre programme en commençant par détailler la fonction main(). La stack frame est mise en place en sauvegardant la valeur courante de RBP en pile et en lui affectant ensuite la valeur courante du registre RSP (sommet de pile courant). Ensuite, de la place est réservée en pile pour la variable locale rc. La convention d'appel imposant un alignement sur un multiple de 16 pour RSP, un « trou » (padding) est créé en soustrayant le contenu de RSP de 16 octets (multiple de 16 le plus proche de la taille de 4 octets de l'entier rc) :

    pushq    %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

On prépare ensuite l'appel à la fonction service(). Le huitième paramètre (la constante 1234567890) est empilé ainsi que l'adresse du septième paramètre "c" via le registre de travail RAX. Ce dernier est situé dans le code segment référencé par RIP, car la chaîne de caractères est readonly, tout comme les chaînes "a" et "b" passées par les registres plus loin :

.LC3:
    .string    "c"
[...]
    pushq    $1234567890        # Param#8 (1234567890) de service()
    leaq    .LC3(%rip), %rax
    pushq    %rax               # Param#7 ("c") de service()

Ensuite, les six premiers paramètres sont mis dans les registres associés conformément à la convention d'appel susmentionnée et la fonction service() est appelée via l'instruction call qui empile implicitement l'adresse de retour :

.LC1:
    .string    "b"
.LC2:
    .string    "a"
[...]
    leaq    .LC1(%rip), %r9    # Param#6 ("b") de service()
    leaq    .LC2(%rip), %r8    # Param#5 ("a") de service()
    movl    $4, %ecx           # Param#4 (4) de service()
    movl    $3, %edx           # Param#3 (3) de service()
    movl    $2, %esi           # Param#2 (2) de service()
    movl    $1, %edi           # Param#1 (1) de service()
    call    service

La figure 2 illustre cette première partie du programme.

figure 02 function call

Fig. 2 : Appel de la fonction service().

Dans la fonction service(), le contenu courant du registre RBP est sauvegardé en pile pour servir ensuite à stocker l'adresse courante du sommet de la pile (nouvelle stack frame) :

    pushq    %rbp
    movq    %rsp, %rbp

Comme la fonction appelle printf(), elle a besoin de sauvegarder les registres de stockage des six premiers paramètres pour les utiliser lors de l'appel. De plus, la fonction a une variable locale (l'entier loc affecté avec l'incrémentation du paramètre c). Les sauvegardes sont réalisées en pile, où l'espace à réserver est par conséquent : 4 entiers 32 bits + 2 pointeurs 64 bits + un entier 32 bits = 4 * 4 + 2 * 8 + 4 = 36. Et les contraintes d'alignement imposent la soustraction de 48 octets au contenu de RSP (multiple de 16 le plus proche de 36) :

.LC0:
    .string    "%d %d %d %d %d %p %p %p %lu\n"
[...]
    subq    $48, %rsp          # Réservation de l'espace en pile
    movl    %edi, -20(%rbp)    # Sauvegarde des registres stockant les paramètres
    movl    %esi, -24(%rbp)
    movl    %edx, -28(%rbp)
    movl    %ecx, -32(%rbp)
    movq    %r8, -40(%rbp)
    movq    %r9, -48(%rbp)
    movl    -28(%rbp), %eax    # EAX = contenu de "c"
    addl    $1, %eax           # Incrémentation de "c"
    movl    %eax, -4(%rbp)     # Mise à jour de "loc" avec le résultat précédent
    movl    -32(%rbp), %edi
    movl    -4(%rbp), %esi
    movl    -28(%rbp), %ecx    # Param#4 ("c") de printf()
    movl    -24(%rbp), %edx    # Param#3 ("b") de printf()
    movl    -20(%rbp), %eax
    pushq    24(%rbp)          # Param#10 ("ul") de printf()
    pushq    16(%rbp)          # Param#9 ("str2") de printf()
    pushq    -48(%rbp)         # Param#8 ("str1") de printf()
    pushq    -40(%rbp)         # Param#7 ("str0") de printf()
    movl    %edi, %r9d         # Param#6 ("d") de printf()
    movl    %esi, %r8d         # Param#5 ("loc") de printf()
    movl    %eax, %esi         # Param#2 ("b") de printf()
    leaq    .LC0(%rip), %rdi   # Param#1 (format) de printf()
    movl    $0, %eax
    call    printf@PLT         # Appel de printf()

La figure 3 illustre l'état de la pile pendant l'exécution de la fonction service() juste avant l'appel à printf().

figure 03 function exec

Fig. 3 : Exécution de la fonction service().

Les sauvegardes des paramètres en pile sont ensuite effacées en incrémentant RSP de 32 octets, la valeur 0 de retour de la fonction est stockée dans le registre EAX (entier 32 bits) et l'instruction leave met le contenu de RBP dans RSP pour dépiler les variables locales et recharge RBP avec le contenu du sommet courant de la pile (valeur de sauvegarde de RBP). Puis l'instruction ret dépile le sommet de la pile (adresse de retour) dans le registre RIP pour retourner à l'adresse située après l'appel de la fonction service() dans main() :

    addq    $32, %rsp
    movl    $0, %eax
    leave
    ret

Le nouvel état de la pile illustré en figure 4 est identique à celui de la figure 2, mais avec l'adresse de retour en moins au sommet. Cette dernière a été chargée dans le registre RIP pour pointer sur l'instruction se trouvant après call dans la fonction main().

figure 04 function ret

Fig. 4 : Retour dans la fonction main().

De retour dans la fonction main(), les septièmes et huitièmes paramètres passés à service() sont dépilés (ajout de 16 au contenu du registre RSP pour dépiler les huit octets de la constante de type unsigned long et les huit octets du pointeur sur la chaîne de caractères "c") :

    addq    $16, %rsp

La pile se présente finalement comme indiqué en figure 5.

figure 05 function after call

Fig. 5 : Après le dépilement des paramètres passés à service().

Le code de retour de la fonction (contenu du registre RAX) est mis dans la variable locale rc. On notera que les entiers étant sur 32 bits, on utilise EAX pour n'extraire que 32 bits du registre RAX :

    movl    %eax, -4(%rbp)

1.3 Notion de coroutine

Par le truchement de sauvegardes et restaurations des registres du processeur, il est possible de mettre en œuvre plusieurs flux d'exécution dans un programme. Chacun de ces flux est une coroutine qui peut se suspendre provisoirement (opération yield) au profit d’une autre. Elles s'exécutent en alternance. Une coroutine reprend son exécution juste après son dernier point de suspension. On ne parle pas de parallélisme, mais de concurrence, car une et une seule coroutine s'exécute à un instant donné. La figure 6 schématise le déroulement de deux coroutines au sein d'un programme.

figure 06 coroutines alt

Fig. 6 : Alternance de coroutines au sein d'un programme.

Toutes les coroutines s'exécutent sur le cœur où opère le thread courant du programme. C'est l'algorithme de séquencement (scheduling) choisi par le programmeur (et non par le système d'exploitation !) qui déterminera l'ordre d'exécution des coroutines.

2. Mise en œuvre

Pour le langage C, différentes implémentations non natives des coroutines sont disponibles. [4] en fait un tour d'horizon non exhaustif. Elles sont plus ou moins portables d'une plateforme matérielle à l'autre, car la sauvegarde des registres n'est pas une opération proposée par les langages de haut niveau tels que le C. En effet, cela requiert des instructions assembleur spécifiques au processeur. Il existe certes des solutions dans le langage, dont [6] qui s’inspire astucieusement du duff's device [7]. Mais elles montrent de nombreuses limitations et lacunes. Une autre option est de s'appuyer sur les fonctions standardisées de la librairie C, comme setjmp() et longjmp() pour sauvegarder des contextes d'exécution (dont les registres du processeur). Dans cet article, nous faisons le choix d'utiliser les fonctions similaires suivantes [8] :

int getcontext(ucontext_t *ucp);
int setcontext(const ucontext_t *ucp);
void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);
int swapcontext(ucontext_t *oucp, const ucontext_t *ucp);

Pour implémenter des coroutines, nous allons au préalable étudier le code source de ces fonctions.

2.1 Le contexte

Les primitives utilisent un contexte de type ucontext_t. Pour l'architecture x86_64, il est défini comme suit dans sysdeps/unix/sysv/linux/x86/sys/ucontext.h :

typedef struct ucontext_t
  {
    unsigned long int __ctx(uc_flags);
    struct ucontext_t *uc_link;
    stack_t uc_stack;
    mcontext_t uc_mcontext;
    sigset_t uc_sigmask;
    struct _libc_fpstate __fpregs_mem;
    __extension__ unsigned long long int __ssp[4];
  } ucontext_t;

Il sert à sauvegarder/restaurer l'état des registres entiers et flottants (champs uc_mcontext et __fpregs_mem), la pile (champ uc_stack) ainsi que le masque de signaux du thread appelant (champ uc_sigmask). Nous n'utiliserons pas les autres champs dans la suite.

2.2 Sauvegarde de contexte

La fonction getcontext() effectue une opération de sauvegarde du contexte courant dans une structure ucontext_t passée en paramètre. Le code source de la fonction getcontext() se trouve dans sysdeps/unix/sysv/linux/x86_64/getcontext.S. Conformément à la convention d'appel de fonction, l'adresse de la structure passée en paramètre est dans le registre RDI.

À l'entrée de la fonction, l'adresse de retour dans la fonction appelante est en sommet de pile, comme indiqué en figure 7.

La première partie sauvegarde l'état courant des registres du processeur dans le contexte. La macro-instruction o<nom de registre>(%rdi) indique l'offset de sauvegarde du registre dans la structure ucontext_t référencée par RDI :

ENTRY(__getcontext)
[...]
    movq    %rbx, oRBX(%rdi)
    movq    %rbp, oRBP(%rdi)
    movq    %r12, oR12(%rdi)
[...]
    movq    %rcx, oRCX(%rdi)
    movq    %r8, oR8(%rdi)
    movq    %r9, oR9(%rdi)

La seconde partie effectue un traitement spécifique pour les registres RSP et RIP. La sauvegarde de RSP va contenir l'adresse du sommet de la pile juste avant l'adresse de retour dans l'appelant (contenu de RSP + 8) et la sauvegarde de RIP va contenir l'adresse de retour dans l'appelant située en sommet de pile :

    movq    (%rsp), %rcx
    movq    %rcx, oRIP(%rdi)
    leaq    8(%rsp), %rcx        /* Exclude the return address. */
    movq    %rcx, oRSP(%rdi)

La troisième partie réalise la sauvegarde des registres flottants :

    leaq    oFPREGSMEM(%rdi), %rcx
    movq    %rcx, oFPREGS(%rdi)
    /* Save the floating-point environment. */
    fnstenv    (%rcx)
    fldenv    (%rcx)
    stmxcsr oMXCSR(%rdi)

La quatrième partie effectue l'appel système rt_sigprocmask() pour sauvegarder le masque de signaux courant. Le synopsis de ce service est :

int rt_sigprocmask(int how, const kernel_sigset_t *set, kernel_sigset_t *oldset, size_t sigsetsize)

On note au passage que la convention d'appel des appels système diffère de la convention d'appel des fonctions. Les paramètres sont passés comme suit :

  1. RAX contient le numéro de l'appel système ;
  2. Les appels système ont au maximum six paramètres ;
  3. Les arguments sont passés du premier au dernier respectivement dans les registres RDI, RSI, RDX, R10, R8 et R9 ;
  4. Le code de retour de l'appel est mis dans RAX.

Le numéro de l'appel système (constante __NR_rt_sigprocmask) est stocké dans le registre EAX, le paramètre how (registre RDI) reçoit la constante SIG_BLOCK, le paramètre set (registre RSI) reçoit NULL (0), le paramètre oldset (registre RDX) reçoit l'adresse de l'emplacement de la sauvegarde du masque de signaux dans le contexte et le dernier paramètre sigsetsize (registre R10) reçoit la constante _NSIG8 qui spécifie la taille des paramètres set et oldset :

    leaq    oSIGMASK(%rdi), %rdx
    xorl    %esi,%esi
[...]
    movl    $SIG_BLOCK, %edi
[...]
    movl    $_NSIG8,%r10d
    movl    $__NR_rt_sigprocmask, %eax
    syscall

La cinquième étape vérifie le retour de l'appel système. Ce dernier retourne 0 en cas de succès ou un code d'erreur négatif. Comme spécifié en commentaire dans sysdeps/unix/sysv/linux/x86_64/sysdep.h, certains appels système comme lseek() retournent une valeur très grande qui pourrait être interprétée comme négative, alors qu'ils se terminent avec succès. On ne peut donc pas comparer la valeur de retour avec 0. Afin de pallier le problème, une convention a été mise en place pour faire en sorte que les retours erreur des appels système soient dans l'intervalle [-4095,-1]. D'où le test suivant qui détecte une erreur si la valeur ‑4095 est supérieure au code de retour de l'appel système se trouvant dans RAX :

    cmpq    $-4095, %rax          /* Check %rax for error. */
    jae    SYSCALL_ERROR_LABEL    /* Jump to error handler if error. */

Enfin, en cas de succès du service, l'entier 32 bits de valeur 0 (résultat de l'opération XOR du registre EAX sur lui-même) est retourné à l'appelant dans le registre EAX :

    /* All done, return 0 for success. */
    xorl    %eax, %eax
    ret
PSEUDO_END(__getcontext)

En résumé, à l'issue de cette fonction, le paramètre ucontext est renseigné comme indiqué en figure 7 : l'état courant des registres ainsi que le masque de signaux courant y sont sauvegardés. Deux des registres prennent des valeurs particulières : le registre RSP (sommet de pile) référence le sommet de pile situé juste avant l'adresse de retour et le registre RIP contient l'adresse de retour dans la fonction où l'appel à getcontext() a eu lieu.

figure 07 getcontext

Fig. 7 : La fonction getcontext().

2.3 Sauvegarde de pile

La fonction makecontext() est un complément de la précédente, dans la mesure où elle reçoit en paramètre un contexte préalablement renseigné par getcontext() et donne la possibilité de définir une nouvelle pile, ainsi qu'une adresse de retour dans une fonction. Cette dernière reçoit un nombre variable de paramètres. Dans le mode d'adressage à plat de l'architecture x86_64, l'adresse de base stockée dans le registre SS (Stack Segment) est fixe. Pour passer d'une pile à l'autre, il suffit de mettre à jour les registres RSP et RBP. La fonction est écrite en langage C et se trouve dans le fichier sysdeps/unix/sysv/linux/x86_64/makecontext.c. La pile est passée dans le champ uc_stack du contexte. Son type est défini dans sysdeps/unix/sysv/linux/bits/types/stack_t.h :

typedef struct
  {
    void *ss_sp;
    int ss_flags;
    size_t ss_size;
  } stack_t;

Le champ ss_flags n'est pas utilisé tandis que les champs ss_sp et ss_size contiennent respectivement l'adresse et la taille de la zone mémoire de la pile.

Le début de la fonction détermine le début de la pile qui se trouve à l'adresse la plus haute de l'espace mémoire pointé par ss_sp :

void __makecontext (ucontext_t *ucp, void (*func) (void), int argc, ...)
{
[...]
  greg_t *sp;
  unsigned int idx_uc_link;
  va_list ap;
  int i;
 
  /* Generate room on stack for parameter if needed and uc_link. */
  sp = (greg_t *) ((uintptr_t) ucp->uc_stack.ss_sp + ucp->uc_stack.ss_size);

On réserve de la place pour les paramètres à empiler s'il y en a plus que six, vu que par convention, les six premiers paramètres passent par des registres. On réserve aussi une entrée supplémentaire pour y mettre la valeur du champ uc_link qui peut pointer sur le contexte que la fonction trampoline [9], évoquée plus bas, utilisera pour effectuer une commutation de contexte :

sp -= (argc > 6 ? argc - 6 : 0) + 1;

Comme l'adresse de la pile doit être alignée sur un multiple de 16 octets, les 4 bits de poids faible sont forcés à 0 pour arrondir au multiple inférieur. La valeur est ensuite décrémentée de huit octets pour réserver une entrée supplémentaire pour l'adresse de la fonction trampoline. Il s'agit d'une fonction interne à la glibc (nommée __start_context()) dans laquelle on aboutira si la fonction spécifiée en paramètre se termine.

  /* Align stack and make space for trampoline address. */
  sp = (greg_t *) ((((uintptr_t) sp) & -16L) - 8);

La variable locale sp est désormais l'adresse du sommet courant de la pile. Par la suite, elle est utilisée comme une table servant à renseigner les entrées réservées dans la pile. La variable locale idx_uc_link est l'index dans cette table de l'entrée où sera stockée l'adresse du contexte suivant (valeur du champ uc_link). La valeur de cet index dépend du nombre de paramètres à passer à la fonction, car uc_link doit être empilé juste avant les paramètres, si le nombre de ces derniers est supérieur à six. C'est 1 si la fonction n'a pas plus de six paramètres (donc, aucun paramètre en pile, car les six premiers seront dans les registres), auquel on ajoute le nombre de paramètres à empiler moins 6 :

  idx_uc_link = (argc > 6 ? argc - 6 : 0) + 1;

Le contexte passé en paramètre est mis à jour : l'adresse de la fonction passée en argument est mise dans la sauvegarde de RIP pour la déclencher lorsque ce contexte sera mis en service, l'emplacement dans la pile du champ uc_link est mis dans la sauvegarde de RBX et le sommet courant de la pile est mis dans la sauvegarde de RSP :

  /* Setup context ucp. */
  /* Address to jump to. */
  ucp->uc_mcontext.gregs[REG_RIP] = (uintptr_t) func;
  /* Setup rbx.*/
  ucp->uc_mcontext.gregs[REG_RBX] = (uintptr_t) &sp[idx_uc_link];
  ucp->uc_mcontext.gregs[REG_RSP] = (uintptr_t) sp;

L'adresse de la fonction trampoline est mise en sommet de pile et la valeur du champ uc_link à l'index calculé plus haut :

  sp[0] = (uintptr_t) &__start_context;
  sp[idx_uc_link] = (uintptr_t) ucp->uc_link;

Les six paramètres à passer à la fonction sont mis dans les sauvegardes des registres associés dans le contexte et en pile au-dessus de l'emplacement de uc_link pour les paramètres supplémentaires (au-delà du sixième, conformément à la convention d'appel de fonction) :

  va_start (ap, argc);
[...]
  for (i = 0; i < argc; ++i)
    switch (i)
      {
      case 0:
         ucp->uc_mcontext.gregs[REG_RDI] = va_arg (ap, greg_t);
         break;
[...]
      case 5:
         ucp->uc_mcontext.gregs[REG_R9] = va_arg (ap, greg_t);
         break;
      default:
         /* Put value on stack. */
         sp[i - 5] = va_arg (ap, greg_t);
         break;
      }
  va_end (ap);
}

La figure 8 schématise l'état de la pile et du contexte à la sortie de makecontext().

v-figure 08 makecontext

Fig. 8 : La fonction makecontext().

Ainsi façonnés, la pile et les registres sauvegardés dans le contexte reproduisent un état où l'on s'apprête à appeler la fonction passée en argument à makecontext() à partir du tout début de la fonction trampoline __start_context() :

__start_context(void)
{
func(arg#0, arg#1, arg#2…);
...Code de __start_context()…
}

Lorsque la fonction se termine, on exécute par conséquent le code du trampoline qui est défini dans sysdeps/unix/sysv/linux/x86_64/__start_context.S. Cette dernière a pour mission d'activer le contexte suivant pointé par uc_link s'il est différent de 0 ou d'appeler exit() pour terminer le programme.

Le but de la fonction trampoline est de restaurer le contexte pointé par le champ uc_link via setcontext(). Nous n'utiliserons pas la fonction trampoline par la suite (car on n'ira jamais au terme de la fonction passée à makecontext()). Nous la décrivons tout de même pour aller au bout de la présentation de makecontext().

Elle commence donc par positionner le sommet de la pile à l'adresse de sauvegarde de uc_link. On rappelle que la fonction précédente a mémorisé cette adresse dans le registre RBX. Cela a pour conséquence de dépiler les paramètres passés à la fonction précédente :

ENTRY(__start_context)
[...]
    movq    %rbx, %rsp

La pile se présente donc comme en figure 9.

figure 09 start context

Fig. 9 : La fonction __start_context().

Le registre RDI est chargé avec la valeur de uc_link de sorte à, si sa valeur est non nulle, servir de premier paramètre à la fonction setcontext() afin de restaurer le contexte pointé par uc_link. Si la valeur est 0, un appel à exit() est réalisé pour terminer le programme. Le retour de setcontext() est testé, car faisant appel à rt_sigprocmask() pour restaurer le masque de signaux, elle peut échouer. Son code d'erreur se trouve dans le registre RAX :

    movq    (%rsp), %rdi        /* This is the next context. */
    testq    %rdi, %rdi
    je    2f            /* If it is zero exit. */
    call    __setcontext
[...]
    movq    %rax,%rdi
2:
    call    HIDDEN_JUMPTARGET(exit)
[...]
L(hlt):
    hlt
END(__start_context)

2.4 Restauration de contexte

Le service setcontext() évoqué dans le paragraphe précédent se trouve dans sysdeps/unix/sysv/linux/x86_64/setcontext.S. Il effectue l'opération inverse à getcontext(). En d'autres termes, il positionne les registres du processeur et le masque de signaux avec les valeurs stockées dans le contexte passé en paramètre. Nous ne détaillerons pas son fonctionnement, car il ne sera pas utilisé dans la suite de notre exposé. Nous utiliserons la fonction swapcontext() définie dans sysdeps/unix/sysv/linux/x86_64/swapcontext.S. Elle effectue une commutation d'un contexte vers un autre. Elle correspond en fait à un getcontext() pour sauvegarder le contexte courant dans le premier paramètre et un setcontext() pour restaurer un contexte à partir du second paramètre.

Il est inutile de commenter la première partie de la fonction qui va jusqu'à l'appel système rt_sigprocmask(), étant donné que cela correspond à la fonction setcontext() vue plus haut pour sauvegarder le contexte courant (registres et masque de signaux) dans la zone passée en premier paramètre.

ENTRY(__swapcontext)
[...]
    /* Save the current signal mask and install the new one with
       rt_sigprocmask (SIG_BLOCK, newset, oldset,_NSIG/8). */
    leaq    oSIGMASK(%rdi), %rdx
    leaq    oSIGMASK(%rsi), %rsi
    movl    $SIG_SETMASK, %edi
    movl    $_NSIG8,%r10d
    movl    $__NR_rt_sigprocmask, %eax
    syscall

Dans la seconde partie du service, c'est un setcontext(), non encore étudié, qui est réalisé pour restaurer le contexte correspondant au second paramètre passé à la fonction.

Le registre R12 (sauvegarde du registre RSI faite quelques lignes plus haut) contient l'adresse du contexte de destination. Il est provisoirement mis dans RDX :

    movq    %r12, %rdx

Les registres flottants et entiers du contexte de destination sont restaurés. La commutation de pile s'opère implicitement avec la restauration de RSP et RBP :

    movq    oFPREGS(%rdx), %rcx
    fldenv    (%rcx)
    ldmxcsr oMXCSR(%rdx)
    /* Load the new stack pointer and the preserved registers. */
    movq    oRSP(%rdx), %rsp
    movq    oRBX(%rdx), %rbx
[...]
    movq    oR14(%rdx), %r14
    movq    oR15(%rdx), %r15

Le registre RIP du contexte est mis en sommet de pile pour retourner dans la fonction qui a renseigné ce contexte (donc à une adresse située juste après un appel à getcontext(), makecontext() ou swapcontext()) :

    movq    oRIP(%rdx), %rcx
    pushq    %rcx

Les registres utilisés pour les six premiers paramètres de la fonction sont restaurés :

    movq    oRDI(%rdx), %rdi
    movq    oRSI(%rdx), %rsi
    movq    oRCX(%rdx), %rcx
    movq    oR8(%rdx), %r8
    movq    oR9(%rdx), %r9
[...]
    movq    oRDX(%rdx), %rdx

EAX est mis à 0 avec une opération XOR de son contenu sur lui-même pour indiquer un retour sans erreur du service :

    xorl    %eax, %eax

L'opération ret dépile l'adresse tout juste mise en sommet de la nouvelle pile pour retourner dans l'appelant à partir duquel le contexte de destination a été sauvegardé :

    ret
PSEUDO_END(__swapcontext)

La figure 10 résume l'opération réalisée.

v-figure 10 context switch

Fig. 10 : La commutation de contexte.

3. Exemples d'utilisation

Après l'étude détaillée (certes, quelque peu rébarbative) de leur fonctionnement interne, mettons en pratique ces routines.

3.1 Commutation de contexte

Le programme switch_ctx met en œuvre une fonction main() et deux fonctions func1() et func2() écrites selon le même schéma.

static ucontext_t ctx_main, ctx_1, ctx_2;
 
void func1(void)
{
  static int done = 0;
 
  getcontext(&ctx_1);
  if (done == 0) {
    done = 1;
    return;
  }
 
  while(1) {
    printf("func1 is running\n");
    swapcontext(&ctx_1, &ctx_main);
  }
}
 
void func2(void)
{
[...] // Idem à func1() mais avec ctx_2
}
 
int main(void)
{
  int c = 0;
 
  func1();
  func2();
 
  while(1) {
    if (getchar() == EOF) {
      printf("Exiting\n");
      break;
    }
    c = (c + 1) % 2;
    if (1 == c) {
      swapcontext(&ctx_main, &ctx_1);
    } else {
      swapcontext(&ctx_main, &ctx_2);
    }
  }
 
  return 0;
}

Les fonctions sont appelées en début de programme pour initialiser leurs contextes respectifs (ctx_1 et ctx_2). Le premier appel est différencié des appels suivants grâce à la variable statique done qui vaut 0 la première fois, puis vaut 1. À leur retour, la fonction main() entre dans une boucle qui effectue des allers et retours entre le contexte ctx_main et les contextes ctx_1 et ctx_2 une fois sur deux via le service swapcontext(). Au premier changement de contexte dans chaque fonction, la variable statique done, désormais égale à 1, permet d'entrer dans une boucle infinie qui affiche le message "func[1|2] is running", puis de retourner dans le contexte ctx_main. La combinaison de touches <CRTL> + <D> termine le programme, car elle provoque le retour de la valeur EOF par la fonction getchar() afin de sortir de la boucle du programme principal :

$ ./switch_ctx
<RETURN>
func1 is running
<RETURN>
func2 is running
<RETURN>
func1 is running
<RETURN>
func2 is running
<CTRL+D>
Exiting

Le programme se compose de trois flux d'exécution alternés. Le premier se déroule dans la fonction main() avec le contexte ctx_main, tandis que les deux autres sont respectivement dans les fonctions func1() et func2() avec les contextes ctx_1 et ctx_2. À partir du second appel, les fonctions func1() et func2() ne vont jamais à leur terme. Elles ne font que rendre la main au flux d'exécution de la fonction main(). Le passage d'un flux à l'autre (yield) est réalisé via l'appel à swapcontext(). Nous venons d'écrire un programme composé de trois coroutines.

3.2 Coroutines sans pile

switch_ctx2 est une évolution du programme précédent avec l'ajout de l'affichage des variables locales value1 et value2 respectivement dans func1() et func2(). Au second appel de la fonction, les variables locales sont respectivement initialisées avec les valeurs 1 et 2. Ayant vu précédemment que ces fonctions ne rendent plus la main à partir de leur second appel, on peut espérer que les variables locales vont garder leurs valeurs respectives.

[...]
void func1(void)
{
  static int done = 0;
  int value1;
 
  getcontext(&ctx_1);
  if (done == 0) {
    done = 1;
    return;
  }
 
  value1 = 1;
    while(1) {
    printf("func1 is running, value1@%p = %d\n", &value1,value1);
    swapcontext(&ctx_1, &ctx_main);
  }
}
 
void func2(void)
{
  static int done = 0;
  int value2;
 
  getcontext(&ctx_2);
  if (done == 0) {
    done = 1;
    return;
  }
 
  value2 = 2;
  while(1) {
    printf("func2 is running, value2@%p = %d\n", &value2, value2);
    swapcontext(&ctx_2, &ctx_main);
  }
}
[...]

À l'exécution, le programme affiche les valeurs suivantes :

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

On note que les deux premiers affichages sont cohérents (1 et 2). Ils correspondent aux premiers sauts dans les fonctions. La figure 11 représente les valeurs de value1 et value2 :

figure 11 varloc init

Fig. 11 : Initialisation des variables locales.

Mais les sauts suivants aboutissent à des valeurs inattendues. Ici, nous obtenons la valeur 2 (mais c'est dépendant du code généré par le compilateur et de la version de la librairie C) ! Nous faisons en fait face à un écrasement de contexte en pile. En effet, au premier saut dans la fonction func1(), la variable locale value1 est initialisée à 1. Puis de func1(), un saut est opéré dans la boucle while() de main() où un appel à getchar() est effectué. Cette fonction, en installant sa stack frame, se retrouve au même endroit dans la pile que func1(). D'où la possible altération des variables locales (clobbered variables) de cette dernière. De même, la stack frame de l'appel à swapcontext() pour aller dans le flux de func2() prend la place de celle de getchar(). Les valeurs en pile à cet endroit sont de nouveau possiblement altérées. Puis un saut dans le contexte de func2(), dont la stack frame se retrouve aussi au même endroit, fait que value2 est initialisée à 2. Cette dernière prend la place de value1 dans la pile, vu que func1() et func2() fonctionnent selon le même schéma, donc avec un code identique ! On a donc des flux d'exécution concurrents qui opèrent au même endroit dans la pile : l'adresse affichée pour value1 et value2 est la même (0x7ffdbeec2874). La figure 12 représente les mêmes valeurs altérées à partir du second saut, qui va dans les boucles while() et n'effectue donc plus d'initialisation des variables locales.

figure 12 clobbered varloc

Fig. 12 : Altération des variables locales.

En résumé, le contenu des variables locales n'est valable qu'avant le changement de flux d'exécution. Une variable locale est considérée comme invalide lors du retour dans un flux d'exécution. Nous avons sans le savoir mis en œuvre des coroutines dépourvues de pile (stackless). En d'autres termes, les coroutines func1() et func2() n'ont pas leur pile propre, mais s'exécutent sur la pile du programme principal (le flux principal). Elles ont leur utilité dans certains environnements où l’on veut consommer le moins de ressources possible et optimiser les temps de commutation de contexte. À partir de telles coroutines, il n'est bien entendu pas non plus possible de changer de contexte d'exécution à partir d'une sous-fonction, car au retour dans le flux, les informations d'appel de la fonction et de retour dans son appelant seront aussi endommagées !

3.3 Coroutines avec pile

Il est bien entendu possible de créer des coroutines avec leur propre pile (stackful). Il faut l'ajouter au contexte du flux à l'aide de makecontext(), comme indiqué dans le programme switch_ctx3 :

static ucontext_t ctx_main, ctx_1, ctx_2;
 
void func1(void)
{
  int value1 = 1;
 
  while(1) {
    printf("func1 is running, value1@%p = %d\n", &value1, value1);
    swapcontext(&ctx_1, &ctx_main);
  }
}
 
void func2(void)
{
[...] // Idem func1 avec la variable locale value2
}
 
int main(void)
{
  int c;
  char *stack1 = malloc(16384);
  char *stack2 = malloc(16384);
 
  getcontext(&ctx_1);
  ctx_1.uc_stack.ss_sp = stack1;
  ctx_1.uc_stack.ss_size = 16384;
  ctx_1.uc_stack.ss_flags = 0;
  ctx_1.uc_link = 0;
  makecontext(&ctx_1, func1, 0);
 
  getcontext(&ctx_2);
  ctx_2.uc_stack.ss_sp = stack2;
  ctx_2.uc_stack.ss_size = 16384;
  ctx_2.uc_stack.ss_flags = 0;
  ctx_2.uc_link = 0;
  makecontext(&ctx_2, func2, 0);
 
  c = 0;
  while(1) {
    if (getchar() == EOF) {
      printf("Exiting\n");
      break;
    }
    c = (c + 1) % 2;
    if (1 == c) {
      swapcontext(&ctx_main, &ctx_1);
    } else {
      swapcontext(&ctx_main, &ctx_2);
    }
  }
[...]
  return 0;
}

Les contextes des flux d'exécution sont créés dans la fonction main(). Et ils sont complétés avec les piles allouées dynamiquement à l'aide de makecontext(). Lors de l'étude du code source de ce service, nous avons vu que le contexte passé en paramètre est complété avec la pile dans laquelle est installé la stack frame d'appel d'une fonction (ici, respectivement func1() et func2()) pour qu'un saut dans ce contexte se traduise par un appel à la fonction. Ainsi, les différents contextes de notre programme sont chacun associés à une pile spécifique. Les variables locales dans chacun d'eux n'entrent plus en conflit, car chaque flux opère avec sa pile propre. D'ailleurs, les adresses affichées montrent que value1 et value2 ne sont plus localisées au même endroit :

$ ./switch_ctx3
<RETURN>
func1 is running, value1@0x5562e0dde264 = 1
<RETURN>
func2 is running, value2@0x5562e0de2274 = 2
<RETURN>
func1 is running, value1@0x5562e0dde264 = 1
<RETURN>
func2 is running, value2@0x5562e0de2274 = 2
<CTRL+D>
Exiting

La figure 13 illustre le fonctionnement.

figure 13 stackful behaviour

Fig. 13 : Coroutines avec pile.

Conclusion

Les fonctions détaillées dans cet article, bien que toujours disponibles dans les récentes versions de la glibc, ont été déclarées obsolètes dans la spécification POSIX [8]. Mais l'intérêt de cette étude était avant tout pédagogique, afin de comprendre le principe et les détails de la sauvegarde et de la restauration des registres et de la pile, pour créer différents flux d'exécution au sein d'un programme.

Nous avons aussi aperçu la terminologie associée aux coroutines. Le séquencement est réalisé avec une opération yield et il existe deux grandes familles de coroutines (stackless et stackful). Dans le second opus, nous reviendrons sur ces aspects, en abordant tous les principes techniques qui régissent les coroutines à travers l'implémentation d'une couche logicielle de niveau supérieur, de sorte à avoir une API similaire à ce qu'on peut trouver nativement dans des langages comme Python, Kotlin ou C++. L'écriture d'applications à flux d'exécution multiples sera ainsi grandement facilitée.

Références

[1] Melvin Conway : https://en.wikipedia.org/wiki/Melvin_Conway

[2] Langages supportant les coroutines : https://en.wikipedia.org/wiki/Coroutine#Programming_languages_with_native_support

[3] Coroutines in C++ : https://en.cppreference.com/w/cpp/language/coroutines

[4] A Survey of Asynchronous Programming Using Coroutines in the Internet of Things and Embedded Systems : https://arxiv.org/abs/1906.00367

[5] Conventions d'appel des fonctions sur architecture Intel : https://en.wikipedia.org/wiki/X86_calling_conventions

[6] Coroutines in C : https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

[7] Duff's device : https://en.wikipedia.org/wiki/Duff%27s_device

[8] Les fonctions set/get/make/swapcontext : https://en.wikipedia.org/wiki/Setcontext

[9] Fonction trampoline : https://en.wikipedia.org/wiki/Trampoline_(computing)



Article rédigé par

Abonnez-vous maintenant

et profitez de tous les contenus en illimité

Je découvre les offres

Déjà abonné ? Connectez-vous