Ce mois-ci, nous espérons encore ravir les amateurs de techniques internes au noyau en vous proposant ces deux brèves. Le premier sujet dissèque et synthétise le travail proposé par Ingo Molnar, destiné à apporter la gestion des appels système asynchrones dans le noyau, et montre comment en tirer parti dans les applications. Le second se penche sur la couche réseau et expose une nouvelle vision de celle-ci, imaginée par des chercheurs et des développeurs. Nous nous retrouvons le mois prochain pour la synthèse de la vingt-et-unième mouture de la série 2.6 de notre noyau, qui marquera la dixième édition du Kernel Corner. Saisissant l’occasion offerte par ce chiffre rond, n’hésitez pas à nous soumettre vos opinions sur la rubrique via nos adresses mail !

[Nouvelle fonctionnalité] Syslets/Threadlets ou l’exécution asynchrone des appels système

Introduction

Suite aux discussions sur la façon d’ajouter à Linux le support de l’exécution asynchrone pour les appels système, Ingo Molnar a développé au courant du mois de février, une approche nommée "syslet". La première version publiée définit le concept d’atome de syslet : objet élémentaire représentant un appel système à traiter. Les benchmarks effectués révèlent alors la pertinence de l’approche face aux entrées/sorties synchrones (que ce soit dans le cas où le cache est désactivé ou l’inverse !). La version suivante (la v3 ;), entraîne des modifications majeures au niveau de l’ABI et apporte également une nouvelle fonctionnalité : les threadlets, couche de haut niveau reposant sur les syslets. La version 4 ne contient qu’une modification de l’API des threadlets. La dernière version publiée à ce jour (la v5) apporte principalement le support de l’architecture x86_64.

L’infrastructure des syslets

Avant d’expliquer le fonctionnement des syslets, prenons l’exemple d’une application souhaitant lire tous les fichiers situés dans un répertoire. En utilisant les appels système classiques, lorsqu’elle accède à ces fichiers, il est fort possible qu’ils ne soient pas présents en cache, auquel cas la fonction read va bloquer (ou renvoie une erreur si l’appel est configuré comme non bloquant) jusqu’à ce que le VFS (Virtual File System) ait récupéré les données sur le périphérique de stockage. Il s’agit ici d’un comportement synchrone. C’est l’approche employée pour la quasi-totalité des appels système sous Linux.
L’approche asynchrone donne à l’application l’opportunité de soumettre un traitement au noyau sans bloquer et d’être averti de sa terminaison. Pour cela, l’infrastructure des syslets définit un composant de base appelé " atome ". Il s’agit d’une enveloppe contenant un appel système qui est ensuite soumise au noyau pour qu’il soit exécuté. La soumission se fait au travers de l’appel système sys_async_exec, lequel prend en paramètre un atome.
Voyons à quoi ressemblent ces atomes. Chacun est représenté par une structure contenant le numéro de service noyau à appeler ainsi que ses paramètres. Un membre est également réservé pour la valeur retournée à l’issue de l’exécution. D’autres champs figurent dans cette structure dont le membre next et flags servant respectivement à chaîner les atomes et à contrôler leur flux d’exécution. Ainsi, bien que l’appel système précédent ne prenne qu’un seul atome en paramètre (l’atome initial), plusieurs pourront être exécutés.
Une application, utilisant ces atomes pour communiquer au noyau les services qu’elle requiert, va profiter d’un traitement optimal de ses requêtes. En effet, après la soumission d’un appel système via un atome, le noyau va l’exécuter. S’il ne bloque pas, le comportement est identique au cas synchrone : la fonction retourne à l’espace utilisateur. Par contre, s’il bloque, c’est-à-dire que les données ne sont pas disponibles (cachemiss), le noyau va appeler schedule (c.-à-d. l’ordonnanceur). À cet instant, le sous-système des syslets va récupérer d’une réserve, un cachemiss thread lequel va servir de médium à l’exécution de la suite de l’application alors que le thread actuel exécutera l’appel système bloquant. Ainsi, elle pourra effectuer d’autres traitements en attendant la terminaison de l’appel système.
Nous l’avons mentionné, le chaînage des atomes permet à l’application d’envoyer en un tout plusieurs appels système. Leur flux d’exécution est conditionné par les flags de chaque atome. Ainsi, il est possible de créer de petits " programmes " (ou scripts) s’exécutant en espace noyau (sans avoir à retourner en espace utilisateur avant la fin de l’exécution).
Reprenons notre exemple. Nous souhaitons lire l’ensemble des fichiers dans un répertoire. En utilisant les syslets, nous avons seulement à créer un atome avec le flag SYSLET_STOP_ON_NON_POSITIVE. Ainsi, la fonction read est exécutée en boucle dans le noyau jusqu’à ce que tout le fichier soit lu. Nous pouvons aussi ajouter le flag SYSLET_SKIP_TO_NEXT_ON_STOP et ainsi déclencher l’exécution de l’atome suivant lorsque tout le fichier sera lu (sans pour autant sortir du contexte du noyau). L’atome suivant (chaîné via le membre next) est dans notre cas l’appel système close. A la fin de la lecture d’un fichier, ce dernier est alors automatiquement fermé. Notons que lors de l’exécution de ces atomes, plusieurs cachemiss thread pourront être utilisés (par exemple lors des différentes lectures).
Finissons avec une brève explication sur le fonctionnement de la notification. En effet, l’utilisateur a soumis des appels système au noyau, mais comment prend-t-il connaissance de la fin de leur exécution ? De même, comment récupère-t-il les résultats ? Pour cela, il initialise en espace utilisateur, via la fonction async_head_init, une structure struct async_head_user contenant principalement un tampon mémoire circulaire. Lorsqu’il soumet ensuite les appels système qu’il souhaite effectuer via sys_async_exec, il passe également la structure précédente en paramètre. Lorsque le noyau termine l’exécution d’un appel système, il inscrit dans la première entrée libre du tampon, l’adresse de l’atome correspondant. À la charge ensuite de l’utilisateur de libérer les entrées (en leur affectant la constante NULL) après en avoir pris connaissance, car le noyau n’écrira pas de nouvelles valeurs si le tampon est rempli. Il renverra à la place un code d’erreur.
Afin d’être alerté quant à la terminaison d’un ou plusieurs atomes, l’utilisateur peut se mettre en attente sur la fonction sys_async_wait qui prend en paramètre le nombre minimum d’atomes devant s’être terminés avant de retourner.
Vous l’avez certainement remarqué, l’utilisation des syslets est astucieuse et peut révéler quelques complexités de mise en œuvre. C’est le prix à payer pour un outil efficace et offrant de nombreuses possibilités. Néanmoins, l’utilisation de cette infrastructure est plutôt destinée aux bibliothèques se devant de fournir à leurs utilisateurs un service performant. Ainsi, une couche de plus haut niveau a été ajoutée et met à la disposition des applications une interface plus accessible. C’est ce que nous allons voir dans la prochaine partie.

La couche des Threadlets

Les threadlets ont été conçues à la suite des critiques sur la complexité d’utilisation des syslets. Ainsi, les threadlets représentent une sur-couche à l’infrastructure des syslets, dans laquelle le concept des atomes est masqué à l’utilisateur. L’utilisation directe des syslets reste pertinente dans les cas où nous souhaitons ne faire aucun compromis entre la facilité d’utilisation et les performances.
Pour exécuter nos appels système de façon asynchrone, il suffit dorénavant d’écrire dans une fonction le code dont l’exécution est appelée à être asynchrone. Cette fonction est alors nommée " threadlet ". Elle doit respecter un prototype particulier et se terminer par la fonction threadlet_complete. Nous l’exécutons ensuite via la fonction threadlet_exec.
L’application profite donc d’un parallélisme étant établi à la volée en fonction du besoin (c.-à-d. des blocages éventuels des appels système). Ce dernier est déterminé de façon optimale au sein du noyau. Avant de continuer dans l’explication, illustrons cela par un bout de code issu d’un exemple donné par Ingo Molnar :

long my_threadlet_fn(void *data)
{
        char *name = data;
        int fd;
        fd = open(name, O_RDONLY);
        if (fd < 0)
                goto out;
        fstat(fd, &stat);
        read(fd, buf, count)
        ...
out:
        return threadlet_complete();
}
main()
{
        done = threadlet_exec(threadlet_fn, new_stack, &user_head);
        if (!done)
                reqs_queued++;
}

La fonction threadlet_exec prend en argument la threadlet, mais également deux autres paramètres. new_stack est un pointeur sur une zone mémoire qui servira, si besoin, comme pile pour les threads créés lorsqu’un ou plusieurs appels système bloquent dans la threadlet. Le dernier argument user_head est l’adresse de la structure dont nous avons déjà parlé, contenant le tampon circulaire pour la notification de la terminaison des appels asynchrones.
Cette fonction retourne la valeur 1 dans le cas où la threadlet s’est déroulée sans blocage. Par contre, si un appel système bloque, un nouveau thread est créé pour poursuivre l’exécution de la threadlet. Le thread original attend, quant à lui, la terminaison de l’appel système. Notons que la gestion des signaux reste correcte dans ce nouveau thread si des gestionnaires avaient été mis en place (CLONE_SIGNAL et CLONE_SIGHAND sont utilisés).
Précisons que threadlet_exec n’est pas un appel système. Cette fonction fait appel à sys_threadlet_on, véritable appel système qui va demander au noyau de passer en " mode d’exécution asynchrone ", en bref, d’utiliser les syslets.
De même, la fonction threadlet_complete qui termine la threadlet, exécute au final l’appel système sys_threadlet_off qui renvoie 1 dans le cas où l’exécution se passe dans le contexte de l’application, sinon 0. Il s’agit alors d’une exécution dans un thread asynchrone. Auquel cas, la fonction async_thread est appelée afin : (1) d’enregistrer dans le tampon circulaire de l’application, l’évènement relatif au traitement asynchrone qui vient de se terminer, et (2) de replacer le thread dans la réserve utilisée pour les exécutions asynchrones.

Conclusion

Nous avons omis plusieurs détails par souci de simplicité. Nous vous laissons le loisir de parcourir les sources du projets à l’adresse http://redhat.com/~mingo/syslet-patches/ pour compléter votre formation ;) Notez cependant que ce sous-système est toujours en cours d’évolution. Ce n’est que lorsqu’il sera intégré à la mainline, signifiant son entière maturité, qu’il conviendra de l’utiliser.

[RECHERCHE] Pile réseau, Network channels et Grand Unified Flow Cache

Nous faisons à nouveau un tour dans le monde de la recherche gravitant autour du noyau Linux, et nous penchons cette fois sur la pile réseau. Extrêmement complète sous Linux, elle intègre bien sur la gestion des paquets réseau, mais aussi leur filtrage, classification et surveillance via la solution Netfilter/IPTables ou encore la flexibilité des algorithmes utilisés si l’on pense aux choix possibles dans les protocoles de congestion TCP. Elle n’est pas limitée aux classiques TCP, IP et UDP, mais implémente aussi des protocoles tels que UDP-lite, DCCP, SCTP... Témoignage de la réputation de notre noyau, on le retrouve ainsi dans des équipements professionnels spécifiquement dédiés au réseau : firewalls, routeurs, répartiteurs de charge... Sa gestion du réseau est un des éléments clefs de son succès, mais elle n’est pas exempte de problèmes ou de pistes d’améliorations. Plusieurs personnes se sont intéressées de près à son fonctionnement et à ses problèmes, et des solutions ont été discutées pour améliorer son organisation et ses performances.

I – Fonctionnement et problèmes soulevés

La couche réseau est chargée d’assurer l’acheminement des données entre un pilote d’interface réseau et le destinataire final de ces données (application...). Lors d’une communication réseau, les données se décomposent en paquets. Historiquement, le fonctionnement de Linux voulait qu’à chaque paquet reçu par l’interface réseau physique (carte Ethernet...), une interruption matérielle soit générée envers le gestionnaire d’interruptions du pilote de cette interface. Nous n’expliquerons pas pourquoi c’est une solution coûteuse ; sachons seulement que dans les faits ceci est très consommateur en ressources au fur et à mesure que la charge en débit augmente. Linux 2.6, puis Linux >= 2.4.20, introduisent NAPI (New API), qui apporte à ce niveau une nouvelle manière de traiter les données entrantes. Désormais, pour les pilotes implémentant NAPI, une telle interruption matérielle est générée beaucoup moins fréquemment grâce au polling. Lors d’une première " salve " de paquets, la carte génère effectivement l’interruption ; le pilote en prend connaissance et désactive aussitôt les interruptions pour être " tranquille ". En contrepartie, le pilote implémente une méthode poll() qui est appelée, et qui, pendant n itérations, attend les paquets, décrémentant n à chacun d’entre eux. Une fois n revenu à zéro, les paquets sont traités par la couche réseau, et le pilote accepte à nouveau les interruptions. NAPI a été largement adoptée par les pilotes, ses bénéfices étant prouvés. Notons cependant, car ceci n’est pas innocent, qu’un seul processeur à la fois peut appeler poll().
La couche réseau de Linux stocke les informations sur les paquets et leur destination (routing) dans plusieurs structures de type tables de hachage. Ces structures existantes, visibles dans les fichiers sources include/net/inet_hashtables.h et net/ipv4/inet_hashtables.c, sont communes à toute la pile réseau, et leur code contient de nombreux verrous destinés à respecter l’atomicité des opérations sur système multiprocesseur.
Début 2006, le développeur Van Jacobson, connu pour ses travaux d’amélioration des protocoles TCP/IP, lance le débat sur la pertinence de l’organisation de la couche réseau dans les systèmes Unix lors d’une présentation orale. Dérivé du père d’Unix, MULTICS, le concept de base n’a pas changé depuis 1980 :

• Une pile entièrement en espace noyau : la pile est donc globale et commune à toutes les parties l’utilisant. Sous trop forte charge, le noyau est configuré pour ignorer purement et simplement les paquets qu’il n’a pas le temps de traiter, impactant ainsi tous les services connectés sans distinction. Les applications orientées temps réel s’en trouvent particulièrement pénalisées. Cette pile en espace noyau effectue également des compromis pénalisants dus à sa généricité.
• Un cheminement coûteux : réception d’un paquet par l’interface physique -> interruption matérielle -> réception par le pilote -> interruption logicielle -> skb (socket buffer), classification globale du paquet par le noyau (est-il entrant, sortant, est-il lu par son destinataire ou pas ?) -> passage par le " chemin lent " : Netfilter et/ou routage -> attribution éventuelle à un socket -> read() éventuel par l’application. Plusieurs interruptions soft sont en fait nécessaires au traitement d’un paquet. À chaque étape, changement de contexte, et chaque traitement n’est pas forcément effectué sur le même processeur, ce qui induit de coûteuses opérations de transfert d’informations entre cache (mémoire) et processeur(s). Des améliorations ont été apportées pour attribuer le plus d’étapes possibles du traitement au même processeur, mais une affinité complète n’est pas encore possible.

Vous suivez toujours ? Parfait. Chaque paquet reçu est mis dans une structure, elle-même insérée dans une table de hachage ; ainsi, au niveau TCP, on en distingue trois :

• tcp_bhash (sockets bound, disposant d’une adresse locale) ;
• tcp_ehash (sockets connected);
• tcp_listening_hash (listening, sockets en écoute).

La liste des sockets existants sur un système peut être obtenue via /proc/net/tcp, qui parcourt ces tables. Faisons un test simpliste et grossier. Sur un système bi-Xeon (soit 4 processeurs vus) avec 1600 sockets utilisés :

$time cat /proc/net/tcp > /dev/null

real 0m0.520s
user 0m0.000s
sys 0m0.452s

Le même système, avec 20 sockets utilisés :

$time cat /proc/net/tcp > /dev/null

real 0m0.014s
user 0m0.000s
sys 0m0.008s

Sans aucune prétention quant à la rigueur de ce test, on voit ici que le temps de traverse des tables de hachage, appelées très fréquemment par le code réseau, peut devenir conséquent. Lors du parcours brut d’une telle table, sous Linux, un verrou (read_lock()) est posé à la lecture de chaque élément.
Entre le moment où un paquet est réceptionné par le pilote et celui où il est délivré à l’application en espace utilisateur, le paquet est classifié par le pilote et placé dans une structure au noyau ; si Netfilter est activé, chaque paquet passe dans sa moulinette afin de déterminer s’il correspond à une ou des règles de filtrage mises en place. C’est un gros problème pour Van Jacobson, qu’il appelle slow path.

II – Une solution originale

La présentation de Van Jacobson, les performances ainsi que la réduction du coût en ressources processeur qu’il annonce lancent le débat et l’intérêt autour du concept de " Network Channels " (ou Netchannels). Un Netchannel est un lien direct entre un producteur (le pilote d’interface réseau) et un consommateur (l’application en espace utilisateur) : le flux de données va directement de l’un à l’autre, sans couche(s) intermédiaire(s) en espace noyau. Evgeniy Polyakov, auteur de l’infrastructure Kevent (cf. KC92), développe et prône également l’utilisation de ces canaux réseau. Au niveau implémentation, un canal est principalement une suite de structures paquets (sk_buff). Si Van Jacobson n’a jamais publié aucun code attestant ses dires et fut critiqué sur ce point, les travaux de Polyakov sont publiquement disponibles et régulièrement améliorés dans l’espoir d’aboutir à une implémentation complète. Après une période enthousiaste ayant succédé à la présentation de Van Jacobson et au premier patch de Polyakov, les arguments en faveur des Netchannels ont été démontés un par un par les développeurs sceptiques. Evgeniy Polyakov s’est employé à contre-argumenter longuement, benchmarks à l’appui, pour prouver sa vision, sans que rien n’ait pu réellement être tranché en faveur des uns ou des autres. Parmi les objections soulevées, la latence pouvant être introduite par une exploitation userspace des couches TCP/IP, qui pourrait entraîner un renvoi de paquets de confirmation (paquets ACK) trop tardif. Malgré tout, plusieurs développeurs noyau demeurent très intéressés par cette approche. Notons que Kelly Daly (IBM) et Rusty Russell ont également proposé leur implémentation basée sur les travaux de Van Jacobson.
Actuellement, Polyakov en est à sa vingtième version des netchannels. Du côté noyau, son code assure le suivi de connexion (connection tracking), la NAT (translation d’adresse) et bien sûr le binding et l’implémentation des canaux. Son implémentation en espace utilisateur gère la réception TCP et UDP, le marquage temporel des paquets, le routage, une interface fournissant des sockets au milieu applicatif...
Dans les travaux des deux développeurs, une seule étape s’immisce entre le pilote et le canal : il s’agit de déterminer à quel canal est destiné un paquet. Vous aurez peut-être remarqué que nous n’avons pas parlé de protocole, seulement de transport de flux de données... Effectivement, le modèle des Netchannels laisse le soin à l’espace utilisateur d’implémenter la majeure partie de la couche TCP/IP. Le principe est : décaler l’interprétation du flux le plus proche possible du consommateur, selon le principe que tout le monde n’a pas besoin de la même quantité ou de la même nature de traitements. Polyakov fournit une implémentation en espace utilisateur de pile TCP/IP, encore rudimentaire.
Pour creuser le sujet, le site de Polyakov :
http://tservice.net.ru/~s0mbre/old/?section=projects&item=netchanne

III – Le Grand Unified Flow Cache

Van Jacobson soutient que les structures actuelles, utilisées pour classifier un paquet au sein du noyau, sont une charge inutile. Evgeniy Polyakov va jusqu’à assumer que l’implémentation actuelle du routage dans le noyau n’est pas nécessaire, et est partisan d’une structure unique pouvant supplanter les TCP hashtables, qui serait plus performante, y compris lors de grosses charges en paquets, et surtout ne nécessitant pas de verrous. Rusty Russel, auteur de Netfilter/IPtables, appuie l’idée et imagine une structure appelée Grand Unified Flow Cache (GUFC). Dans la vision des deux développeurs, elle se chargerait uniquement de déterminer le channel à emprunter par un paquet, et le pousserait dans celui correspondant. Le GUFC serait une structure permettant d’identifier de manière unique chaque paquet et sa destination, selon des tuples qui pourraient être organisés ainsi :
adresse source – port source – adresse de destination – port de destination – protocole – source locale ou non – destination locale ou non
Si les caractéristiques d’un paquet entrant correspondent à un tuple du GUFC associé à un Netchannel, le paquet y est immédiatement envoyé, sans passer par aucun autre filtrage ; ceci pourrait être un moyen de court-circuiter le passage de certains flux par Netfilter.
Si plusieurs développeurs de la couche réseau Linux s’accordent sur l’idée, l’implémentation est encore matière à débats enflammés (confinant au troll) sur les algorithmes tels que tables de hachage vs listes vs arbres binaires. Polyakov essaie depuis longtemps de démontrer la supériorité de sa structure en arbre, appelée " trie ", qu’il affirme être exempte de tout besoin de verrouillage.
Dans leur forme actuelle, les Netchannels ne s’accordent pas forcément bien avec le concept de " socket ", mais davantage avec une nouvelle solution d’interfaçage avec les applications, asynchrone ou événementielle (Kevent ?).
Pour conclure sur le sujet des performances de la couche réseau, revenons à l’actualité du noyau.
Dans un futur plus proche, une amélioration qui devrait voir le jour (pour Linux 2.6.22 ou 2.6.23 ?) est la possibilité pour plusieurs threads noyau de lire des paquets depuis une interface réseau simultanément, depuis des processeurs différents. Le travail serait effectué au niveau de NAPI, qui deviendrait alors " multiqueue NAPI ". Enfin, la discussion autour d’une infrastructure permettant d’accéder de manière asynchrone à des ressources telles que fichiers ou sockets bat son plein, entre les Kevents de Polyakov et les threadlets d’Ingo Molnar. Dans certains cas, les performances et la réactivité en bénéficient.