Approche détaillée des futex (partie 2/4)

GNU/Linux Magazine n° 175 | octobre 2014 | Rachid Koucha
Creative Commons
  • Actuellement 0 sur 5 étoiles
0
Merci d'avoir participé !
Vous avez déjà noté cette page, vous ne pouvez la noter qu'une fois !
Votre note a été changée, merci de votre participation !
Après un premier opus sur la notion de futex, ce second article aborde la face cachée du concept de futex dans la mesure où il donne une vue détaillée des traitements réalisés au sein du noyau de Linux. Cette connaissance permet d'utiliser les futex de manière efficace et robuste.

Dans cet article, nous aborderons la gestion des futex dans le noyau, les réglages pour le réveil des threads, l'optimisation intra processus et enfin, la terminaison anticipée des threads.

1. Gestion des futex dans le noyau

La gestion des futex par le noyau Linux est configurable par le drapeau CONFIG_FUTEX (fichier init/Kconfig). Les traitements sont essentiellement effectués dans le fichier source kernel/futex.c. La structure de donnée principale, décrite en figure 1, est une table de hachage [1] nommée futex_queues. Chaque entrée est une structure futex_hash_bucket.

Fig. 1 : Les futex dans le noyau Linux

Le futex dont l'adresse virtuelle est fournie par l'espace utilisateur via l'appel système futex() est converti, par la fonction get_futex_key(), en une clé unique représentée par l'union futex_key définie dans le fichier include/linux/futex.h :

union futex_key {
 struct {
  unsigned long pgoff;
  struct inode *inode;
  int offset;
 } shared;
 struct {
  unsigned long address;
  struct mm_struct *mm;
  int offset;
 } private;
 struct {
  unsigned long word;
  void *ptr;
  int offset;
 } both;
};

Passée à la fonction de hachage hash_futex(), la clé est transformée en index dans la table futex_queues. À chaque entrée de la table de hachage est associée une liste de priorité (plist définie dans le fichier d'en-tête include/linux/plist.h). C'est en fait une liste de listes qui classe ses éléments futex_q par valeur croissante du champ prio (flèches rouges sur la figure 1) et classe les éléments dont le champ prio est identique en « First In, First Out » (FIFO, représenté par les flèches vertes sur la figure 1).

Chaque futex_q est associé via le champ task à un thread en attente sur un futex identifié par sa clé dans le champ key et est alloué dans la pile du thread (i.e. variable locale de l'appel système futex()). Il convient de préciser que du point de vue de l'utilisateur, plus la valeur numérique de la priorité d'un thread est grande, plus il est prioritaire. Il suffit de se reporter au manuel en ligne de l'appel système sched_setscheduler(). Cela est perturbant, car en interne, le noyau Linux et notamment l'ordonnanceur, utilisent la logique inverse. Linux supporte les threads temps réel (politiques d'ordonnancement SCHED_RR et SCHED_FIFO) et les threads temps partagé (politique d'ordonnancement SCHED_OTHER entre autres). Les appels système sched_get_priority_min() et sched_get_priority_max() retournent respectivement les valeurs minimales et maximales pour les priorités en fonction du type d'ordonnancement, comme indiqué dans le tableau de la figure 2.

Fig. 2 : Plages de priorités par politique d'ordonnancement

Les threads temps réel sont toujours plus prioritaires que les threads temps partagé, vu que ces derniers ont la priorité 0 alors que les premiers ont une priorité minimale de 1. Pour garantir un temps de réponse optimal, Linux tient compte de la priorité des threads lors de la mise en file d'attente sur les futex. Par contre, la politique d'ordonnancement n'est pas prise en compte. Comme les files d'attente sont des plist ordonnées par ordre croissant des champs prio, nous sommes dans la logique inverse des significations des priorités pour les threads (du point de vue de l'utilisateur tout au moins !). C'est la raison pour laquelle le champ prio qui sert à ordonner les éléments futex_q, est dérivé de la priorité des threads qui leur sont associés par la formule suivante :

prio = MIN(normal_prio, MAX_RT_PRIO)

avec :

- normal_prio égal :

 - "MAX_RT_PRIO - 1 - priorité" pour les threads temps réel,

 - "100 à 139" pour les threads temps partagé.

- MAX_RT_PRIO égal à 100.

Pour les threads temps réel, la formule utilise les priorités passées par l'utilisateur qui vont de 1 à 99 avec l'appel système sched_setscheduler(). Comme ces valeurs sont inférieures à MAX_RT_PRIO, il en résulte que le champ prio aura respectivement les valeurs de 98 à 0.

Pour les threads temps partagé, la formule utilise la priorité interne au noyau qui va de 100 à 139 en fonction du niceness du thread modifiable par l'appel système nice(). Comme ces valeurs sont supérieures à MAX_RT_PRIO, il en résulte que le champ prio est toujours égal à 100.

Par conséquent, les threads temps réel, sortent toujours de la file en premier par rapport aux threads temps partagé et dans l'ordre du plus prioritaire au moins prioritaire. De plus, quand il y a égalité de priorité, l'algorithme des plistrange les futex_q de manière FIFO. Ce qui implique que les threads temps partagé, tous rangés avec le champ prio égal à MAX_RT_PRIO (100) et les threads temps réel de priorités identiques sont sortis de la liste dans l'ordre du plus anciennement au plus récemment mis en attente.

Pour étayer le propos, le programme futex_prio du listing suivant crée tout d'abord, pour un futex, un emplacement de la taille d'un entier à l'adresse futex_vardans un segment de mémoire partagée via l'appel système mmap(). Ensuite, il crée des processus dont les priorités sont passées en argument. Quand l'argument vaut 0, c'est un processus temps partagé de priorité par défaut qui est créé. Lorsque le paramètre est supérieur à 0 et précédé de la lettre « f » ou « r », c'est un processus de priorité temps réel avec les politiques d'ordonnancement respectives SCHED_FIFO ou SCHED_RR qui est créé. Les processus sont mis en attente, dans l'ordre de leur création, tant que le futex vaut 0. Après avoir passé le futex à la valeur 1, le thread principal réveille un à un les processus endormis en passant 1 en troisième paramètre de l'opération FUTEX_WAKE de l'appel système futex().

[...]
#define futex_wait(addr, val) \
           syscall(SYS_futex, addr, FUTEX_WAIT, val, NULL)

#define futex_wakeup(addr, nb) \
           syscall(SYS_futex, addr, FUTEX_WAKE, nb)

int *futex_var;

int main(int ac, char *av[])
{
pid_t               pid;
unsigned int        i;
int                 prio;
int                 policy;
struct sched_param  param;
const char         *policy_str;

  // Segment de mémoire partagée pour le futex
  futex_var = (int *)mmap(0, sizeof(int),
                          PROT_READ | PROT_WRITE,
                          MAP_SHARED | MAP_ANONYMOUS,
                          -1, 0);

  *futex_var = 0;

  for (i = 1; i < ac; i ++)
  {
    switch(av[i][0])
    {
      case 'r':
      {
        policy = SCHED_RR;
        prio = atoi(&(av[i][1]));
        policy_str = ", RR";
      }
      break;
      case 'f':
      {
        policy = SCHED_FIFO;
        prio = atoi(&(av[i][1]));
        policy_str = ", FIFO";
      }
      break;
      default :
      {
        prio = 0;
        policy_str = "";
      }
    }

    pid = fork();

    // Processus fils
    if (0 == pid)
    {
      if (prio)
      {
        param.sched_priority = prio;
        sched_setscheduler(0, policy, &param);
      }

      futex_wait(futex_var, 0);

      printf("Fils#%d reveille\n", getpid());

      exit(0);
    }

    printf("Fils#%d, priorite %d%s\n", pid, prio, policy_str);
  } // End for

  // On s'assure que tous les fils sont bloqués sur le futex
  sleep(1);

  printf("Changement d'etat du futex\n");

  *futex_var = 1;

  for (i = 1; i < ac; i ++)
  {
    futex_wakeup(futex_var, 1);

    // On laisse le temps au fils d'afficher son message
    sleep(1);
  } // End for

  return 0;
} // main

L'exécution du programme requiert les droits du super-utilisateur (e.g. commande sudo) car, par défaut, Linux n'autorise pas la création de threads temps réel par les utilisateurs non privilégiés.

Dans ce premier exemple d'exécution, quatre threads temps réel sont créés. On constate bien que peu importe la politique d'ordonnancement, les threads sont réveillés dans l'ordre croissant des priorités :

$ gcc futex_prio.c -o futex_prio
$ sudo ./futex_prio f1 f99 r4 r8
Fils#3643, priorite 1, FIFO
Fils#3644, priorite 99, FIFO
Fils#3645, priorite 4, RR
Fils#3646, priorite 8, RR
Changement d'etat du futex
Fils#3644 reveille
Fils#3646 reveille
Fils#3645 reveille
Fils#3643 reveille

Dans ce second exemple, seuls des threads temps partagé sont créés. On constate bien le réveil dans l'ordre FIFO :

$ sudo ./futex_prio 0 0 0 0
Fils#3658, priorite 0
Fils#3659, priorite 0
Fils#3660, priorite 0
Fils#3661, priorite 0
Changement d'etat du futex
Fils#3658 reveille
Fils#3659 reveille
Fils#3660 reveille
Fils#3661 reveille

Dans ce dernier exemple qui est le cas illustré en figure 1, des threads temps réel et temps partagé sont créés. On constate bien le réveil des premiers avant les seconds et l'ordre FIFO pour les threads de mêmes priorités :

$ sudo ./futex_prio r1 f1 0 0 r4 0 r4 0 f67
Fils#3756, priorite 1, RR
Fils#3757, priorite 1, FIFO
Fils#3758, priorite 0
Fils#3759, priorite 0
Fils#3760, priorite 4, RR
Fils#3761, priorite 0
Fils#3762, priorite 4, RR
Fils#3763, priorite 0
Fils#3764, priorite 67, FIFO
Changement d'etat du futex
Fils#3764 reveille
Fils#3760 reveille
Fils#3762 reveille
Fils#3756 reveille
Fils#3757 reveille
Fils#3758 reveille
Fils#3759 reveille
Fils#3761 reveille
Fils#3763 reveille

On notera que l'ordre de réveil des threads établi au moment de la mise en attente sur le futex ne varie pas en cas de changement de priorité, comme le met en exergue le programme suivant qui est une variante du listing précédent. Une fois les processus fils créés et mis en attente sur un premier futex, le processus père inverse leur priorité avec l'opération "100 - prio", puis les réveille. Ensuite, les processus fils se remettent en attente sur un deuxième futex avant d'être de nouveau réveillés par le processus père.

[...]
int main(int ac, char *av[])
{
pid_t               pid[300];
unsigned int        i;
int                 prio;
int                 policy;
struct sched_param  param;
const char         *policy_str;

  // Segment de mémoire partagée pour le futex
  futex_var = (int *)mmap(0, 2 * sizeof(int),
                          PROT_READ | PROT_WRITE,
                          MAP_SHARED | MAP_ANONYMOUS,
                          -1, 0);

  futex_var[0] = futex_var[1] = 0;

  for (i = 1; i < ac; i ++)
  {
[...]
    pid[i] = fork();

    // Processus fils
    if (0 == pid[i])
    {
      if (prio)
      {
        param.sched_priority = prio;
        sched_setscheduler(0, policy, &param);
      }

      // Attente sur le futex 0
      futex_wait(&(futex_var[0]), 0);

      sched_getparam(pid[i], &param);
      printf("Fils#%d reveille avec la priorite %d%s\n", getpid(), param.sched_priority, policy_str);

      // Attente sur le futex 1
      futex_wait(&(futex_var[1]), 0);

      sched_getparam(pid[i], &param);
      printf("Fils#%d reveille avec la priorite %d%s\n", getpid(), param.sched_priority, policy_str);

      exit(0);
    }

    printf("Fils#%d, priorite %d%s\n", pid[i], prio, policy_str);
  } // End for

  // On s'assure que tous les fils sont bloqués sur le futex
  sleep(1);

  // Inversement des priorités de tous les processus en attente
  for (i = 1; i < ac; i ++)
  {
    switch(av[i][0])
    {
      case 'r':
      {
        policy = SCHED_RR;
        prio = atoi(&(av[i][1]));
        policy_str = ", RR";
      }
      break;
      case 'f':
      {
        policy = SCHED_FIFO;
        prio = atoi(&(av[i][1]));
        policy_str = ", FIFO";
      }
      break;
      default :
      {
        prio = 0;
        policy_str = "";
      }
    }

    if (prio)
    {
      printf("Changement de la priorite du Fils#%d de %d%s a %d%s\n",
             pid[i], prio, policy_str, 100 - prio, policy_str);

      param.sched_priority = 100 - prio;
      sched_setscheduler(pid[i], policy, &param);
      }
    }

  } // End for

  printf("Changement d'etat du futex 0\n");

  futex_var[0] = 1;

  for (i = 1; i < ac; i ++)
  {
    futex_wakeup(&(futex_var[0]), 1);

    // On laisse le temps au fils d'afficher son message
    sleep(1);
  } // End for

  printf("Changement d'etat du futex 1\n");

  futex_var[1] = 1;

  for (i = 1; i < ac; i ++)
  {
    futex_wakeup(&(futex_var[1]), 1);

    // On laisse le temps au fils d'afficher son message
    sleep(1);
  } // End for

  return 0;
} // main

L'exécution montre qu'après attente sur le premier futex, l'ordre de réveil ne change pas malgré l'inversement des priorités des processus fils. Les nouvelles priorités ne prennent effet qu'au moment de la mise en attente sur le deuxième futex :

$ gcc futex_prio_1.c -o futex_prio_1
$ sudo ./futex_prio_1 f1 f99 r4 r8
Fils#10728, priorite 1, FIFO
Fils#10729, priorite 99, FIFO
Fils#10730, priorite 4, RR
Fils#10731, priorite 8, RR
Changement de la priorite du Fils#10728 de 1, FIFO a 99, FIFO
Changement de la priorite du Fils#10729 de 99, FIFO a 1, FIFO
Changement de la priorite du Fils#10730 de 4, RR a 96, RR
Changement de la priorite du Fils#10731 de 8, RR a 92, RR
Changement d'etat du futex 0
Fils#10729 reveille avec la priorite 1, FIFO
Fils#10731 reveille avec la priorite 92, RR
Fils#10730 reveille avec la priorite 96, RR
Fils#10728 reveille avec la priorite 99, FIFO
Changement d'etat du futex 1
Fils#10728 reveille avec la priorite 99, FIFO
Fils#10730 reveille avec la priorite 96, RR
Fils#10731 reveille avec la priorite 92, RR
Fils#10729 reveille avec la priorite 1, FIFO

2. Nombre de threads à réveiller

Le troisième paramètre de l'opération FUTEX_WAKE est le nombre de threads à réveiller. Quand on doit gérer plus de deux threads en concurrence, on peut s'interroger sur la valeur à utiliser.

Dans certains cas particuliers, comme les barrières vues en section 3.3 du premier article de cette série, on connaît le nombre de threads en attente et la sémantique du service implique qu'il faut réveiller tous les threads en attente. Dans ce cas, le troisième paramètre sera au moins égal à ce nombre.

Cependant, d'autres services comme les mutex peuvent avoir un nombre indéterminé de threads en attente. On peut vouloir réveiller plusieurs threads, voire tous les threads suspendus pour laisser l'ordonnanceur de Linux choisir le thread qui prendra effectivement le CPU. Dans [2], Ulrich Drepper déconseille de faire toute supposition sur tel ou tel comportement du noyau, car c'est sujet à modifications. Il propose d'utiliser soit la valeur 1, soit la valeur INT_MAXdéfinie dans le fichier d'en-tête <limits.h>, mais pas de valeurs intermédiaires. Toutefois, [2] n'indique pas quelle valeur choisir de préférence entre 1 ou INT_MAX. Avec la connaissance de la gestion des files d'attente sur les futex côté noyau telle que présentée en section 1, il peut être suggéré les choix suivants :

1. Si le futex ne concerne que des threads temps réel avec la politique d'ordonnancement SCHED_FIFO, il est conseillé de spécifier la valeur 1 en troisième paramètre, car c'est le thread de priorité maximum et qui est en attente depuis le plus longtemps (en cas d'égalité de priorité) qui sera réveillé. Il en est de même pour les threads temps réel avec la politique d'ordonnancement SCHED_RR, car s'ils sont en attente sur le futex, cela veut dire qu'ils n'ont pas consommé leur quantum de temps CPU et qu'ils peuvent donc reprendre leur exécution.

2. Si le futex ne concerne que des threads temps partagé, tous les threads sont ordonnés en FIFO sous la même priorité MAX_RT_PRIO. Si on précise la valeur 1, alors on favorise le thread qui est en attente depuis le plus longtemps sans se soucier des priorités réelles des threads. La valeur INT_MAXlaisse, une fois les threads réveillés, l'opportunité à l'ordonnanceur de Linux de choisir le thread non seulement en fonction du temps d'attente sur le futex, mais aussi en fonction de sa priorité réelle qui est recalculée régulièrement en fonction de la consommation CPU antérieure.

3. Si le futex concerne à la fois des threads temps réel et temps partagé, alors il semble que la valeur INT_MAX soit la plus appropriée car à tout moment on sait que si au moins un thread temps réel est en attente sur le futex, alors il sera réveillé en premier et s'il n'y a pas de threads temps réel, alors le cas 2 s'applique.

Bien-entendu, ces règles doivent être pondérées par le temps CPU consommé par un thread pour reprendre le contrôle sur la ressource gérée par le futex et par le nombre potentiel de threads en attente. Sous peine d'être confronté au fameux problème de « thundering herd » évoqué dans [3], il est souvent préférable de ne réveiller qu'un thread à la fois.

3. Optimisation intra processus

Lorsque les threads en compétition sont dans un seul et même processus Linux, il est possible de rendre l'appel système futex() plus efficace en utilisant les versions PRIVATE de certains opérateurs définis dans le fichier d'en-tête <linux/futex.h> :

[...]
#define FUTEX_WAIT_PRIVATE      (FUTEX_WAIT | FUTEX_PRIVATE_FLAG)
#define FUTEX_WAKE_PRIVATE      (FUTEX_WAKE | FUTEX_PRIVATE_FLAG)
[...]

Dans le cas où le futex ne concerne que les threads d'un même processus, les traitements internes au noyau pour identifier la variable (association d'une clé d'identification effectuée par la fonction get_futex_key() dans le fichier kernel/futex.c dont un extrait est donné dans le code suivant) sont moins lourds, car il n'est pas besoin d'identifier la page mémoire ou l'inode associé à l'objet dans lequel se trouve le futex et il n'est même pas besoin d'incrémenter le compteur de référence associé. L'adresse virtuelle suffit à identifier une variable au sein d'un même processus, vu que tous ses threads partagent son espace d'adressage. On parle alors de futex privés par opposition aux futex partagés.

Dans le listing qui suit, les traitements associés aux clés des futex privés est en rouge. Le reste du code, beaucoup plus long et complexe, concerne les clés des futex partagés.

static int get_futex_key(u32 __user *uaddr, int fshared, union futex_key *key, int rw)
{
 unsigned long address = (unsigned long)uaddr;
 struct mm_struct *mm = current->mm;
 struct page *page, *page_head;
 int err, ro = 0;
 /*
 * The futex address must be "naturally" aligned.
 */
 key->both.offset = address % PAGE_SIZE;
 if (unlikely((address % sizeof(u32)) != 0))
 return -EINVAL;
 address -= key->both.offset;
 /*
 * PROCESS_PRIVATE futexes are fast.
 * As the mm cannot disappear under us and the 'key' only needs
 * virtual address, we dont even have to find the underlying vma.
 * Note : We do have to check 'uaddr' is a valid user address,
 * but access_ok() should be faster than find_vma()
 */
 if (!fshared) {
 if (unlikely(!access_ok(VERIFY_WRITE, uaddr, sizeof(u32))))
 return -EFAULT;
 key->private.mm = mm;
 key->private.address = address;
 get_futex_key_refs(key);
 return 0;
 }
again:
 err = get_user_pages_fast(address, 1, 1, &page);
[...]
 if (err == -EFAULT && rw == VERIFY_READ) {
 err = get_user_pages_fast(address, 1, 0, &page);
 ro = 1;
 }
 if (err < 0)
 return err;
 else
 err = 0;
[...]
 page_head = compound_head(page);
 if (page != page_head) {
 get_page(page_head);
 put_page(page);
 }
[...]
 lock_page(page_head);
[...]
 if (!page_head->mapping) {
 int shmem_swizzled = PageSwapCache(page_head);
 unlock_page(page_head);
 put_page(page_head);
 if (shmem_swizzled)
 goto again;
 return -EFAULT;
 }
[...]
 if (PageAnon(page_head)) {
[...]
 if (ro) {
 err = -EFAULT;
 goto out;
 }
 key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */
 key->private.mm = mm;
 key->private.address = address;
 } else {
 key->both.offset |= FUT_OFF_INODE; /* inode-based key */
 key->shared.inode = page_head->mapping->host;
 key->shared.pgoff = page_head->index;
 }
 get_futex_key_refs(key);
out:
 unlock_page(page_head);
 put_page(page_head);
 return err;
}

À titre d'exemple, dans la GLIBC/NPTL, ce sont les versions PRIVATE des opérations qui sont utilisées par défaut pour les futex se cachant derrière les mutex ou les barrières. Pour une utilisation par des threads appartenant à différents processus, les services pthread_mutexattr_setpshared() et pthread_barrierattr_setpshared() permettent de positionner l'attribut PTHREAD_PROCESS_SHARED afin de passer par les versions non PRIVATE des opérations sur les futex.

4. Terminaison anticipée des threads

Lorsque des threads sont en attente sur un futex parce qu'un ou plusieurs autres threads ont pris la main dessus, il peut arriver la situation où les threads détenant le mutex se terminent sans réveiller les threads en attente. Par exemple, une erreur de programmation qui aboutirait à la terminaison d'un thread qui détient un mutex. C'est un cas d'étreinte fatale [4] pour les threads en attente sur le futex concerné, car ils ne seront plus réveillés !

À titre d'exemple, le programme futex_robust du listing suivant crée deux processus fils : le premier se met en attente sur un futex tant que ce dernier est à 0, le second le met à 1, mais ne réveille pas les threads en attente dessus avant de se terminer. Le thread principal attend la fin du second processus, puis du premier, via l'appel système waitpid().

[...]
#define futex_wait(addr, val) \
           syscall(SYS_futex, addr, FUTEX_WAIT, val, NULL)

#define futex_wakeup(addr, nb) \
           syscall(SYS_futex, addr, FUTEX_WAKE, nb)

int *futex_var;

int main(int ac, char *av[])
{
pid_t pid1, pid2;

  // Segment de mémoire partagée pour le futex
  futex_var = (int *)mmap(0, sizeof(int),
                          PROT_READ | PROT_WRITE,
                          MAP_SHARED | MAP_ANONYMOUS,
                          -1, 0);

  *futex_var = 0;

  pid1 = fork();

  // Le premier processus fils se met en attente sur le futex
  if (0 == pid1)
  {
    futex_wait(futex_var, 0);

    printf("Fils#%d reveille\n", getpid());

    exit(0);
  }

  // On s'assure que le fils est bloqué sur le futex
  sleep(1);

  pid2 = fork();

  // Le second processus fils passe le futex à la valeur 1
  // mais ne réveille pas le premier fils avant de se terminer !
  if (0 == pid2)
  {
    *futex_var = 1;

    printf("Changement d'etat du futex : 0x%x\n", *futex_var);

    exit(0);
  }

  printf("Attente du second fils#%d\n", pid2);
  waitpid(pid2, NULL, 0);

  printf("Second fils#%d termine\n", pid2);

  printf("Attente du premier fils#%d\n", pid1);
  waitpid(pid1, NULL, 0);

  printf("Premier fils#%d termine\n", pid1);

  return 0;
} // main

À l'exécution, le programme ne se termine pas, car le processus principal reste en attente infinie sur la fin du premier fils, qui lui-même est en attente infinie sur le futex non libéré par le second fils :

$ gcc futex_robust.c -o futex_robust
$ ./futex_robust
Changement d'etat du futex : 0x1
Attente du second fils#13042
Second fils#13042 termine
Attente du premier fils#13041

Pour pallier le problème, Linux propose la notion de listes robustes (i.e. « robust lists ») décrite succinctement dans la documentation fournie avec ses sources : Documentation/robust-futexes.txt. Le principe consiste à passer au noyau une liste de futex occupés par les threads en espace utilisateur. Au moment de la terminaison des threads, le noyau parcourt cette liste pour identifier les futex occupés sur lesquels au moins un thread est en attente, afin de déclencher l'opération FUTEX_WAKE pour un seul des threads en attente (i.e. comme lorsque l'on passe la valeur 1 en troisième paramètre de l'appel système).

Conformément à la description donnée en section 1, c'est le thread le plus prioritaire ou le plus anciennement mis en attente en cas d'égalité de priorités, qui est réveillé. La mise en œuvre n'est pas triviale au premier abord. Une ABI (i.e. « Application Binary Interface ») est définie dans la documentation des sources : Documentation/robust-futex-ABI.txt.

Pour aider à la compréhension, le code suivant est une nouvelle version du programme précédent : les lignes de code différentes sont en rouge.

[...]
#define set_robust_list(l, s) syscall(SYS_set_robust_list, l, s)

struct udata_t
{
  struct robust_list link;
  int                futex_var;
} *udata;

struct robust_list_head head;

int main(int ac, char *av[])
{
pid_t pid1, pid2;

  head.list.next = (struct robust_list *)&(head.list);
  head.futex_offset = offsetof(struct udata_t, futex_var);
  head.list_op_pending = 0;
  set_robust_list(&head, sizeof(struct robust_list_head));

  // Segment de mémoire partagée pour le futex
  udata = (struct udata_t *)mmap(0, sizeof(struct udata_t),
                          PROT_READ | PROT_WRITE,
                          MAP_SHARED | MAP_ANONYMOUS,
                          -1, 0);

  udata->futex_var = 0;

  pid1 = fork();

  // Le premier processus fils se met en attente sur le futex
  if (0 == pid1)
  {
    set_robust_list(&head, sizeof(struct robust_list_head));

    udata->futex_var |= FUTEX_WAITERS;

    futex_wait(&(udata->futex_var), udata->futex_var);

    printf("Fils#%d reveille : futex_var = 0x%x\n", getpid(), udata->futex_var);

    exit(0);
  }

  // On s'assure que le fils est bloqué sur le futex
  sleep(1);

  pid2 = fork();

  // Le second processus fils verrouille le futex avec son pid
  // mais ne réveille pas le premier fils avant de se terminer !
  if (0 == pid2)
  {
    set_robust_list(&head, sizeof(struct robust_list_head));

    head.list_op_pending = &(udata->link);

    udata->futex_var |= getpid();

    printf("Changement d'etat du futex : 0x%x\n", udata->futex_var);

    udata->link.next = head.list.next;
    head.list.next = &(udata->link);
    head.list_op_pending = (struct robust_list *)0;

    exit(0);
  }

  printf("Attente du second fils (pid#%d)\n", pid2);
  waitpid(pid2, NULL, 0);

  printf("Second fils#%d termine\n", pid2);

  printf("Attente du premier fils#%d\n", pid1);
  waitpid(pid1, NULL, 0);

  printf("Premier fils#%d termine\n", pid1);

  return 0;
} // main

La figure 3, qui schématise l'organisation des données en mémoire durant l'exécution du programme, sert de support pour la description des modifications.

Fig. 3 : Organisation des données en mémoire

4.1. La structure de données de l'utilisateur

L'application doit prévoir une structure de données qui embarque le futex et les pointeurs pour la liste chaînée. D'où la structure udata_t qui contient respectivement les champs futex_var et link. Le type struct robust_list est défini dans le fichier d'en-tête <linux/futex.h> :

struct robust_list {
        struct robust_list *next;
};

Afin d'ajouter ou supprimer efficacement en O(1) n'importe quel élément de la liste, il est conseillé d'utiliser un double chaînage, sinon on devra parcourir tout ou partie de la liste pour retrouver les éléments. Ici, pour simplifier le propos, nous nous contentons d'une liste simplement chaînée, car c'est le minimum requis par le noyau.

4.2. La tête de liste

L'application doit définir et initialiser une tête de liste dont le type est défini dans le fichier d'en-tête <linux/futex.h> :

struct robust_list_head {
        /*
         * The head of the list. Points back to itself if empty:
         */
        struct robust_list list;

        /*
         * This relative offset is set by user-space, it gives the kernel
         * the relative position of the futex field to examine. This way
         * we keep userspace flexible, to freely shape its data-structure,
         * without hardcoding any particular offset into the kernel:
         */
        long futex_offset;

        /*
         * The death of the thread may race with userspace setting
         * up a lock's links. So to handle this race, userspace first
         * sets this field to the address of the to-be-taken lock,
         * then does the lock acquire, and then adds itself to the
         * list, and then clears this field. Hence the kernel will
         * always have full knowledge of all locks that the thread
         * _might_ have taken. We check the owner TID in any case,
         * so only truly owned locks will be handled.
         */
        struct robust_list *list_op_pending;
};

D'où la définition de la variable globale head avec le type robust_list_head et son initialisation en début de fonction main().

Le champ list est une liste circulaire qui pointe sur la structure robust_list des enregistrements qui contiennent le futex. Le champ futex_offset est la valeur à ajouter à l'adresse de la structure robust_list dans l'enregistrement pour retrouver l'adresse du futex. La fonction de service offsetof() est préconisée pour calculer un offset de champ dans une structure donnée. Le champ list_op_pending est l'adresse de la structure robust_list de l'enregistrement qu'on s'apprête à ajouter à la liste juste avant de prendre la main sur le futex ; on verra par la suite son utilité. On notera que la liste circulaire est vide lorsque le champ list pointe sur lui-même.

Il faut ensuite enregistrer la tête de liste au sein du noyau via l'appel système set_robust_list(). Cela a pour conséquence de mémoriser l'adresse de la tête de liste dans le descripteur du thread au sein du noyau. Chacun des threads doit effectuer cette opération et au plus une tête de liste peut être enregistrée par thread. D'où l'invocation de set_robust_list() au début de chaque processus (le principal et les deux secondaires).

4.3. Prise de contrôle sur le futex

Dans le dernier listing de la section 4, c'est le second fils qui prend le contrôle sur le futex (e.g. opération de verrouillage si c'est un mutex). Cela consiste tout d'abord à assigner le champ list_op_pending de la tête de liste avec l'adresse de l'enregistrement associé au futex. Ensuite, il faut renseigner les 29 bits de poids faible du futex avec l'identifiant du thread qui prend le contrôle.

Ici, comme nous avons affaire à trois processus mono-thread, l'identifiant de process est aussi l'identifiant du thread (à ne pas confondre avec l'identifiant retourné par le service POSIX pthread_self() en espace utilisateur !). D'où l'appel à getpid() (cela devrait se faire par opération atomique, mais ce n'est pas justifié dans cet exemple simple, car on sait que le thread concurrent n'accède pas à la variable à ce moment). Enfin, l'enregistrement du futex est inséré dans la liste circulaire, puis le champ list_op_pending est remis à 0.

La prise de contrôle sur le futex (affectation de l'identifiant de thread) et la mise en liste circulaire de l'enregistrement associé n'est pas une opération atomique. S'il arrivait que le thread se termine entre les deux actions (suite à la réception d'un signal de terminaison par exemple), le noyau n'aurait pas le moyen de savoir que le futex est verrouillé et donc, ne réveillerait pas les autres threads en attente. Sur terminaison de thread, une valeur non nulle pour le champ list_op_pending permet au noyau de savoir qu'une opération de verrouillage était en cours et qu'il faut donc procéder au réveil d'éventuels threads en attente.

4.4. Mise en attente sur le futex

Toujours dans le dernier listing de la section 4, c'est le premier fils qui se met en attente. Cela consiste simplement à positionner le bit FUTEX_WAITERS dans la variable du futex. Il faudrait prévoir une opération atomique pour cela, mais ce n'est pas utile dans cet exemple car à ce moment, le thread concurrent n'accède plus au futex. Ensuite, le thread se met en attente sur le futex via l'appel système futex().

4.5. Le réveil du thread en attente

Dans le cas normal, pour libérer le futex, le thread qui a la main dessus doit assigner le champ list_op_pending de la tête de liste avec l'adresse de l'enregistrement associé au futex, enlever l'enregistrement de la liste circulaire, remettre les 29 bits de poids faible à 0 (i.e. remise à 0 de l'identifiant de thread) et, à l'aide de l'opération FUTEX_WAKE de l'appel système futex(), réveiller les threads en attente sur le futex si le bit FUTEX_WAITERS est positionné. Cela doit se faire de manière atomique en général. Enfin, il faut remettre le champ list_op_pending à zéro.

Dans notre exemple simple, nous simulons un arrêt prématuré du thread qui a la main sur la ressource : le second processus se termine sans l'appel système futex() pour réveiller le premier qui est en attente. Le noyau se charge de remédier au problème en parcourant la liste robuste. L'enregistrement correspondant au futex s'y trouvant, il positionne le bit FUTEX_OWNER_DIED en plus du bit FUTEX_WAITERS, remet à 0 les 29 premiers bits (i.e. l'identifiant de thread) et réveille le thread en attente.

Avec ce nouveau comportement, le programme se termine bien à l'exécution :

$ gcc futex_robust_1.c -o futex_robust_1
Changement d'etat du futex : 0x800038fe
Attente du second fils (pid#14590)
Second fils#14590 termine
Attente du premier fils#14589
Fils#14589 reveille : futex_var = 0xc0000000
Premier fils#14589 termine
$

4.6. Limitations

Le protocole imposé par l'ABI restreint l'utilisation de la variable du futex, vu que les 29 bits de poids faible sont destinés à stocker l'identifiant de thread, le bit 29 est réservé pour de futures améliorations, le bit 30 est réservé pour FUTEX_OWNER_DIED et le bit 31 pour FUTEX_WAITERS (cf. figure 4).

Fig. 4 : Format du futex en mode robuste

Des mécanismes d'optimisation du nombre d'appels système futex() tels que vu en section 3.1.2 du premier article de cette série, sont rendus plus difficiles à mettre en place car ils nécessitent de pouvoir stocker différentes valeurs dans la variable. Ce qui est offert ici est un fonctionnement basique du futex : libre (ou déverrouillé) quand les 29 bits de poids faible sont à 0, occupé (ou verrouillé) quand les 29 bits de poids faible sont différents de 0 (i.e. un identifiant de thread y est stocké) avec toutefois la possibilité de voir si des threads sont en attente ou non via le bit FUTEX_WAITERS.

Il a été vu qu'au plus une liste robuste pouvait être enregistrée par thread. Comme ce mécanisme est utilisé par l'extension non POSIX pthread_mutexattr_setrobust_np() avec le drapeau PTHREAD_MUTEX_ROBUST_NP pour rendre un mutex robuste, il en résulte que ces services sont prohibés dans les applications liées à la librairie GLIBC/NPTL. Avec cette dernière, le service pthread_mutex_lock() retourne le compte-rendu d'erreur EOWNERDEAD tout en ayant verrouillé le mutex quand il est avéré qu'un thread s'est terminé sans libérer le mutex (i.e. en interne, le bit FUTEX_OWNER_DIED est positionné dans la variable du futex associé). Un exemple est donné dans le listing suivant :

[...]
pthread_mutex_t mutex;

void *thread(void *p)
{
int rc = pthread_mutex_lock(&mutex);

  printf("Thread#%x, rc = %d\n", pthread_self(), rc);

  if (EOWNERDEAD == rc)
  {
    printf("Le proprietaire precedent du mutex est termine sans deverrouillage\n");

    pthread_mutex_unlock(&mutex);
  }

  return NULL;
}

int main(int ac, char *av[])
{
pthread_t           tid1, tid2;
pthread_mutexattr_t attr;

  // Initialisation du mutex
  memset(&attr, 0, sizeof(attr));
  pthread_mutexattr_setrobust_np(&attr, PTHREAD_MUTEX_ROBUST_NP);
  pthread_mutex_init(&mutex, &attr);

  pthread_create(&tid1, NULL, thread, NULL);
  pthread_create(&tid2, NULL, thread, NULL);

  printf("Attente du 1er thread#%x\n", tid1);
  pthread_join(tid1, NULL);

  printf("Attente du 2nd thread#%x\n", tid2);
  pthread_join(tid2, NULL);

  return 0;
} // main

Le programme crée un mutex robuste et deux threads. Celui qui prend la main en premier verrouille le mutex et se termine sans le déverrouiller. Par conséquent, le second reçoit le code d'erreur EOWNERDEAD (de valeur 130) sur le verrouillage :

$ gcc mutex_robust.c -o mutex_robust -lpthread
$ ./mutex_robust
Attente du 1er thread#b7fb7b90
Thread#b7fb7b90, rc = 0
Attente du 2nd thread#b75b6b90
Thread#b75b6b90, rc = 130
Le proprietaire precedent du mutex est termine sans deverrouillage

Utilisée avec ou sans la GLIBC/NPTL, cette fonctionnalité semble surtout destinée à repérer la terminaison anormale d'un thread pendant l'exécution de sa section critique. Le thread réveillé par le noyau aura la plupart du temps la plus grande difficulté à savoir si les données modifiées durant la section critique inachevée sont valides ou non.

Conclusion

Ainsi s'achève la deuxième partie de la série consacrée à l'implémentation dans le noyau de la face cachée des futex. Le prochain opus évoquera la notion d'héritage de priorité, ainsi que le multiplexage.

Références

[1] Principe de la table de hachage : http://fr.wikipedia.org/wiki/Table_de_hachage

[2] « Futex are tricky » par Ulrich Drepper : http://people.redhat.com/drepper/futex.pdf

[3] Thundering herd problem : http://en.wikipedia.org/wiki/Thundering_herd_problem

[4] Notion d'étreinte fatale : http://fr.wikipedia.org/wiki/Interblocage

Tags : C, futex