Retrouvez cet article dans : Linux Magazine 88

De retour pour cette quatrième édition, nous vous proposons pas moins de quatre brèves pour fêter cela ;) Cependant, vous ne trouverez pas cette fois de partie "actualité". La release candidate 1 du noyau 2.6.19 venant tout juste de sortir à l’heure de l’écriture de ces lignes, le prochain numéro sera l’occasion d’y traiter des nouvelles fonctionnalités et mises à jour, plus nombreuses que d’habitude. Pour commencer cette rubrique, un résumé sur les discussions autour de la virtualisation ayant eu lieu lors du Kernel Summit vous est proposé. Nous continuons avec un tour d’horizon sur la problématique entourant Reiser4 ainsi qu’un aperçu de ses fonctionnalités. Pour les apprentis sorciers qui souhaitent s’immerger dans les sources du noyau, une brève décrivant succinctement leur organisation est exposée. Nous finissons avec un développement sur la fonctionnalité smpnice, améliorant la répartition de charge sur un système multiprocesseur (load balancing).

Linux Kernel Summit 2006 : la (para)virtualisation dans le noyau

Partant des conférences du deuxième jour, présentées par une équipe de XenSource, une de chez OpenVZ, puis par Eric Biederman (développeur noyau), la part des discussions sur la virtualisation a été importante lors du Kernel Summit 2006. Tout le monde s’accorde sur l’utilité d’implémenter dans le noyau des supports permettant une virtualisation efficace, mais il reste à trouver un consensus sur ce qui doit être fait exactement. Les solutions proposées ne manquent pas, comme en témoignent les différents jeux de patchs proposés sur la LKML (Xen, IBM, OpenVZ, VMWare...) et les solutions déjà existantes.
Le terme virtualisation regroupe plusieurs approches différentes. Pour expliquer ceci très brièvement, on peut distinguer principalement :

• la "virtualisation complète", qui est en fait l’émulation d’une plate-forme matérielle entière, et est destinée à faire tourner un OS complet sans modification et sans qu’il ait connaissance d’être sur une "fausse" plate-forme. C’est l’approche choisie notamment par VMWare et qemu. Celle-ci n’est pas vraiment dans le sujet, car elle ne nécessite pas de modifications de l’OS hôte ni de l’OS invité (autres que pour les performances), reposant sur un émulateur complet.
• la paravirtualisation à la Xen : on a ici un système hôte minimal, tournant donc réellement sur la plate-forme matérielle, et un ou des OS "invités", qui sont modifiés un peu comme pour supporter une nouvelle architecture matérielle ressemblant à l’x86. Entre les deux, un hyperviseur permet de contrôler l’allocation des ressources matérielles (RAM, temps processeur...) et de traiter les requêtes d’accès dites "privilégiées" (memory-mapping, interrupt handlers). Le cas de Xen a été traité dans le LM87 :-)
• la virtualisation au niveau OS : ici un seul noyau tourne, avec plusieurs systèmes lancés autour, utilisant chacun ce même noyau, ce qui est donc une forme différente de virtualisation, puisque ne permettant pas de lancer un OS basé sur un noyau différent. On peut cependant faire tourner des systèmes différents basés sur le même noyau ou des bibliothèques système personnalisées. La virtualisation est ici constituée par une isolation des ressources et des accès système, qui est cruciale afin d’éviter qu’un système déborde sur ou attaque les autres. Cette technique nécessite évidemment un noyau directement conçu pour offrir une séparation des accès aux ressources. Les espaces virtualisés sont ici couramment appelés des "partitions", ou encore "containers". C’est la technique présente sous Solaris 10, ou encore utilisée par OpenVZ, et on peut voir des technologies comme le Jail sous FreeBSD ou le chroot Linux comme des cousins rudimentaires (cloisonnement partiel accès et pas de quantification de ressources allouées). Cette méthode de virtualisation est la plus performante, elle nous affranchit de la présence d’un hyperviseur.

Quelles ont été les solutions débattues pendant le Kernel Summit ? L’équipe de XenSource propose depuis un certain temps une série complète de patchs pour inclusion dans le noyau. Bien que l’atout de Xen soit d’être la seule solution de paravirtualisation open source, ces patchs lui sont spécifiques et ne répondent pas aux besoins d’autres solutions. Les développeurs noyau s’accordent sur le fait que l’inclusion d’un système de virtualisation au sein du noyau doit être générique afin de satisfaire tous les acteurs du domaine, réservant donc aux patchs Xen un accueil en demi-teinte.
De son côté, VMWare souhaite intégrer un système complexe appelé VMI (Virtual Machine Interface) proposant, au travers d’une interface stable, un certain nombre de fonctions bas niveau (désactivation des interruptions, modification des attributs des pages, etc.) susceptibles d’être appelées par un hyperviseur ou le noyau et implémentées au sein d’un fichier binaire chargé au démarrage : la VMI ROM. Cette infrastructure formerait ainsi un framework de paravirtualisation qui pourrait être commun à plusieurs solutions. Elle a été froidement accueillie, car étant potentiellement destinée à faire tourner des machines virtuelles ou des hyperviseurs sous forme de binaires propriétaires. La réponse apportée à VMI (la proposition de VMWare) est paravirt_ops de Rusty Russell (IBM), qui reste dans l’idée d’une couche destinée à accueillir un hyperviseur s’il le faut. Dans ce cas, si un tel composant implémente les interfaces fournies par le jeu de fonctions paravirt_ops, il se charge du traitement, sinon ce sont les fonctions habituelles du noyau qui sont exécutées. Techniquement, paravirt_ops apporte une surcouche de pointeurs vers des fonctions et ce qu’elles appellent est choisi à la compilation : appels système ou hyperviseur. C’est un ensemble non figé, donc aucune compatibilité entre versions dans le temps n’est garantie, ce qui limite la possibilité d’y lier du code binaire.
Un système de containers serait également une solution rassemblant beaucoup d’avis, une série de patchs a été soumise par Eric Biederman, qui prône une solution de namespaces. Un namespace désigne un sous-système entier tel qu’identifié par Eric Biederman : réseau, système de fichiers, gestion des processus... Son objectif est de faire tourner plusieurs instances d’un même sous-système dans le noyau. Ces sous-systèmes étant en général liés, ils seraient regroupés pour former un conteneur.
IBM souhaite plutôt des containers orientés applications, qui ne virtualisent donc pas forcément un système complet, tandis que l’équipe OpenVZ souhaite des containers qui ressemblent autant que possible à un système réel.
A l’heure où ces lignes sont écrites, les namespaces, VMI, Xen et paravirt_ops sont tous candidats à l’inclusion dans le noyau. Nous ne pouvons donc donner pour l’instant le dénouement de l’histoire. La virtualisation est un sujet d’actualité pour Linux, mais qui progresse lentement.

Le système de fichiers Reiser4 : pourquoi, et quand ?

Le sujet est revenu récemment dans les unes de l’actualité Linux : le système de fichiers de Hans Reiser, dans sa version 4, totalement réécrite, va-t-il être inclus dans le noyau ? La conjoncture y étant favorable, tentons ici de faire un point sur les caractéristiques techniques de ce FS, et de résumer les raisons qui ont autant retardé son inclusion. En 2002, Hans Reiser, architecte du système de fichiers ReiserFS alors en version 3 (il n’y a jamais eu de version 1 ou 2 de publiée), se lance dans une quatrième version, qui ne reprend pas le code existant et sera incompatible avec les précédentes. Les objectifs et fonctionnalités sont ambitieux. Le nouveau FS se veut être non seulement le plus rapide, mais aussi entièrement modulaire et évolutif.

NUMA : Non Uniform Memory Architecture, une architecture mémoire pour systèmes multiprocesseurs où les zones mémoires sont séparées et placées en différents endroits (et différents bus) vis à vis de chaque processeur, les temps d’accès différant suivant la zone accédée.

La structure de base du système de fichiers

ReiserFS3 utilisait une structure en arbre (balanced tree) ; il introduit pour Reiser4 la notion de dancing tree, un dérivé proche qui, selon lui, offre des avantages supplémentaires en termes de performances. C’est le premier objectif de ce nouveau FS. Intéressons-nous de plus près à ces structures en arbre, en particulier celles dites "balanced trees" (arbres équilibrés). Cette structure contient au minimum ce qui permettra de localiser et caractériser un fichier : chemin, nom, emplacement sur le disque (bloc de début du fichier, nombre de blocs occupés). Plusieurs autres systèmes de fichiers, comme XFS ou JFS, utilisent des structures en arbres équilibrés. On emploie l’adjectif "équilibré" pour signifier que chaque nœud a une hauteur (nombre de niveaux inférieurs) à respecter (à n près) vis-à-vis des autres nœuds…

ReiserFS utilise 5 niveaux de nœuds, le plus bas stockant les données (nœuds BLOB, Binary Large Objects).
Reiser4 améliore le concept, en réduisant l’arbre d’un niveau, stockant les données dans les leaf nodes (niveau1). Ce stockage s’effectue dans des structures de niveau 1 différentes selon la taille du fichier, et c’est l’abandon du cinquième niveau qui cause l’incompatibilité structurelle entre la série 3 nommée "ReiserFS" et dernière série, nommée "Reiser4". Mais commençons par le début. Dans un système de fichiers Reiser, le nœud racine (niveau 4) est le point de départ de tout accès à l’arbre. Les deux niveaux suivants sont assez similaires dans leur principe pour que l’on s’abstienne de détailler. Un nœud branch node (niveau 3) ou un nœud twig node (niveau2) regroupe un ensemble de structures relativement simples appelées "items".
Un item est toujours composé d’un en-tête et d’un corps. L’en-tête a la structure suivante :

Chaque item possède une clef, unique dans la majorité des cas (les situations dans lesquelles ce paradigme n’est pas vérifié seront passées sous silence par votre serviteur). Les clefs sont triées sur un même niveau par ordre ascendant, ce qui permet une recherche efficace. Reiser4 peut être vu comme deux couches : la couche de stockage, qui est l’ensemble de ce que nous venons de décrire, et la couche sémantique, qui fait la liaison entre un nom de fichier et la(les) clé(s) associée(s).
Il existe plusieurs types d’items, chacun sera traité par l’extension associée au pluginID.
Aux niveaux 2 et 3 de l’arbre, l’item (soit extent pointer, soit node pointer) contient des liens vers les nœuds enfants.
Le niveau 1 représente le stockage des données, un de ses nœuds pouvant être :

• un unfleaf (unformatted leaf node), qui est un nÅ“ud qui contient uniquement des données, est dit "non formaté", car pas de découpage en items. Un ensemble d’unfleaves se suivant dans leur numéro de bloc peuvent former un extent. C’est la méthode de stockage des "gros" fichiers.

• un nÅ“ud formaté (formatted node), qui sera un ensemble d’items. Certains items stockent en leur corps des données brutes. Ils sont utilisés pour les petits fichiers < 1 bloc. On trouve également un type d’item appelé "cmpnd_dir_item", qui matérialise un répertoire et contient les clés identifiant les fichiers contenus dans ce répertoire.

Le dancing tree de Reiser4 est en fait un arbre équilibré, dont l’équilibrage ne se réorganise qu’au moment des écritures sur disque (flush), requises par un sync() ou un commit de transaction. C’est à ce moment que Reiser4 va réorganiser son arbre par parties, pour rassembler plusieurs très petits fichiers (<4 K) dans un seul nœud. C’est également à cet instant que les blocs disque seront réservés pour accueillir les données, par opposition à la majorité des autres systèmes de fichiers où cette opération est effectuée plus tôt ; cette technique, inspirée par XFS, est appelée "allocate-on-flush". Elle permet ainsi de grouper beaucoup plus de demandes d’allocation, réduisant ainsi les accès disque et permettant d’optimiser la fragmentation pour les fichiers souvent modifiés.
Une particularité bien connue des systèmes de fichiers de Hans Reiser est l’optimisation du traitement des petits fichiers. Pour des raisons internes à Linux que nous ne traiterons pas ici, la taille par défaut d’un bloc de stockage est de 4 Ko et est difficilement modifiable sans toucher au cœur de notre OS. Le comportement d’un système de fichiers traditionnel, pour des raisons de simplicité, est de stocker au maximum un fichier par bloc. Prenons un exemple type simple : si vous regardez le résultat d’un ls -lsh /etc, vous constaterez immédiatement qu’une bonne quantité de ses membres ont une taille bien inférieure à 4 Ko. Les systèmes de fichiers Ext allouant un bloc complet pour chacun d’entre eux, vous imaginez maintenant la place perdue sur le disque. Par curiosité, j’ai effectué le test sur mon système, une distribution Desktop standard :

# find / -type f -size -4k | wc -l 140932

On a ainsi 140932x4=563728 Ko occupés sur le disque par des fichiers faisant tous moins de 4 Ko.
Dans toutes ses versions, le système de fichiers Reiser groupe les petits fichiers ensemble dans un même bloc, réduisant au maximum la perte de place.

Spécificités et nouveaux concepts

Hormis cette structure d’arbre dansant, qui est au final une modification mineure du concept d’arbre équilibré, Reiser4 offre de réelles innovations par rapport aux autres systèmes de fichiers et à ses propres versions précédentes.
Vous vous souvenez peut-être que dans le schéma d’un en-tête d’item présenté précédemment, on trouve un champ nommé "pluginId". Initialement, Reiser4 prévoit un système de fichiers entièrement modulaire. Ainsi, par un système de plugins, il est possible de redéfinir la structure et le comportement de chaque item. Chaque type d’item correspond à une extension. Même les notions de fichiers et de répertoires sont traitées par des plugins, que rien ne vous interdit de changer ou modifier. Au niveau du stockage de données, Hans Reiser prévoit par exemple des plugins permettant de compresser ou chiffrer des données.
Reiser4 est également connu pour sa notion de "métadonnées". Traditionnellement, on accède au contenu d’un fichier par des opérations standards (lecture au niveau FS dudit fichier), et les différents attributs associés à ce fichier (propriétaire, ACL, xattrs...), les métadonnées, sont récupérés par un procédé distinct. Reiser4 pousse plus loin encore le concept Unix selon lequel tout est fichier, en exposant les métadonnées selon un ensemble totalement évolutif et consultable par les opérations habituelles d’accès aux fichiers. Comme vous n’avez peut-être rien compris à cette précédente phrase, passons à la pratique : sous Reiser4, un fichier est aussi un dossier qui héberge ses métadonnées, originellement dans le sous-dossier metas. Pour connaître par exemple le propriétaire d’un fichier, vous pouvez effectuer :

$ cat photo_xxx.jpg/metas/uid 1000

Enfin, c’est un système de fichiers intégrant la notion de "transactions". Elle a pour but qu’après n’importe quel événement inattendu, comme un crash ou une coupure brutale d’électricité, le système de fichiers se trouve dans un état cohérent : on valide ou annule les dernières modifications en cours. Cependant Reiser4 rompt ici encore avec la tradition qui veut que les transactions soient localisées dans un emplacement spécifique et réservé de la partition, appelé "journal". Pour résumer, dans un système de fichiers dit "journalisé", une opération d’écriture ou de modification est d’abord écrite dans le fichier journal et, lors de la validation de la transaction (phase appelée "commit"), est réécrite à l’endroit où elle était physiquement censée se produire. Afin d’éviter ces deux écritures, Reiser4 ne définit pas de journal à un endroit précis. La modification est écrite, et, lors de sa validation, on change simplement l’endroit vers lequel le ou les items associés pointaient depuis l’ancien emplacement des données vers celui où la transaction a été effectivement écrite : c’est la notion de "wandering log".

Controversé à plusieurs niveaux

Présent dans la branche d’Andrew Morton (-mm) depuis deux ans, Reiser4 n’a toujours pas été intégré au noyau officiel. Il a déchaîné les débats sur la Linux Kernel Mailing List, dus en partie à ses aspects techniques, mais aussi à la forte personnalité de son architecte en chef, j’ai nommé Hans Reiser.
Par certains aspects, le code de reiser4 redéfinit des tâches habituellement effectuées par la couche VFS. Son système de plugins a aussi été considéré comme dangereux d’une part, puisque permettant à n’importe qui de modifier des aspects du FS, donc potentiellement de remonter des bugs finalement uniquement liés à l’utilisation d’extensions non officielles. D’autre part, les développeurs noyau ont jugé qu’il serait nettement plus judicieux de placer ce système au niveau de la couche VFS, afin que cette possibilité de plugins soit potentiellement accessible d’une manière unique à tout système de fichiers. Par ailleurs, à l’heure actuelle reiser4 ne supporte pas les attributs étendus (xattrs), ne permettant pas d’utiliser SELinux avec ce FS, ni les Entrées/Sorties directes (direct I/O), qui permettent des opérations sur les fichiers sans passer par le tampon de cache du système de fichiers (utilisé en particulier par les SGBD pour améliorer leurs performances). Les quotas ne sont pas non plus gérés. Le principe d’accès aux métadonnées, selon lequel un fichier est aussi un répertoire qui les contient, n’a pas fait l’unanimité. Il engendre des problèmes de verrous et la question de savoir si un nom de répertoire ‘metas’ présent systématiquement et non modifiable n’est pas problématique.
Face aux critiques, Hans Reiser a, pendant un temps, manqué de diplomatie et celles-ci se sont transformées en discussions agressives. Des développeurs noyau, échaudés par son attitude, sont devenus réfractaires aux discussions avec lui et à la relecture du code. Accusé de plus de ne pas avoir effectué convenablement la maintenance de ReiserFS (version 3), la confiance des développeurs noyau dans sa capacité à maintenir et corriger les bugs de Reiser4 est mitigée.
Cependant, durant l’été les discussions ont repris sur la LKML pour relecture du code et inclusion dans le noyau officiel, sur un ton cordial et avec un Hans Reiser plus humble et attentif. Depuis, le système de fichiers a subi des modifications conséquentes en vue de cette éventuelle entrée dans le noyau : les possibilités de modification du FS par plugins ont été réduites et, s’il est possible que Reiser 4 garde sa propre architecture d’extensions pendant les premiers temps de sa présence dans le noyau, Hans Reiser a été fortement encouragé (entre autres par Linus Torvalds) à migrer celle-ci dans la couche VFS, en concertation avec ses mainteneurs. Le principe de fichier à la fois dossier exposant ses métadonnées a, quant à lui, du être abandonné. Le code a d’une manière générale été modifié pour être en conformité avec le style de codage en vigueur dans le noyau Linux. Désormais, les objections pour l’inclusion de Reiser4 sont minimes et l’ambiance générale y est plutôt favorable. Il est donc fortement probable qu’on puisse le trouver dans une toute prochaine mouture de notre noyau. Qui tient le pari pour le 2.6.20 ? ;-) Pour patienter jusque-là, vous pouvez tester Reiser4 en installant un noyau d’Andrew Morton, qui se présente sous forme d’un patch (ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6) à appliquer aux sources vanilla. Les outils d’administration Reiser4 sont disponibles à l’adresse ftp://ftp.namesys.com/pub/reiser4progs. Pour compléter votre connaissance sur Reiser4, la meilleure source d’information reste le site officiel : www.namesys.com/v4/v4.html.

Répartition des sources du noyau

Certains sous-systèmes (systèmes de fichiers, gestion mémoire et réseau) du noyau possèdent un répertoire propre contenant leurs sources. Nous y revenons par la suite. Le répertoire kernel/ contient toutes les autres fonctionnalités essentielles aux noyaux. Nous y trouvons l’implémentation de l’ordonnanceur et des appels système relatifs (sched.c). Un cas particulier concerne les appels système fork et exit qui possèdent leur propre fichier source de même nom. L’affichage sur la console est gérée dans le fichier printk.c. Nous trouvons également l’infrastructure de gestion du temps (time.c), la gestion des timers (timer.c et hrtimer.c), la gestion des signaux (signal.c), la gestion des modules (module.c), l’infrastructure des "parties basses" des gestionnaires d’interruption (softirq.c), le mécanisme de traitement différé du travail (workqueue.c), l’implémentation des mécanismes de synchronisation (mutex.c, futex.c, spinlock.c, rcupdate.c), et encore quelques autres fonctionnalités.
Comme son nom l’indique, le répertoire init/ contient les sources relatives au démarrage du système (le repérage des partitions, la gestion des ramdisks, etc.).
Le répertoire fs/ contient l’infrastructure du VFS (Virtual File System), un sous-répertoire pour chaque type de système de fichiers, ainsi que l’implémentation de tous les appels système y étant associés. Nous trouvons par exemple l’implémentation de execve et du format ELF (exec.c et binfmt_elf.c), des trois principaux appels système de gestion des fichiers (open.c et read_write.c) et bien d’autres encore. Finalement, un sous-répertoire particulier (partitions/) abrite les sources implémentant la gestion des partitions.
Le répertoire abritant la gestion mémoire se nomme mm/. Toutes les opérations touchant à la mémoire sont définies ici. Notons cependant une exception. L’infrastructure du noyau est organisée en deux parties : une générique (de loin la plus grosse) résidant dans les répertoires décrits et, une autre, spécifique à chaque type d’architecture résidant dans arch/[Type d’architecture] et include/asm-[Type d’architecture]. La gestion de la mémoire a donc bien évidemment une partie spécifique pour chaque type d’architecture.
Décrivons à présent le contenu de mm/. L’implémentation de l’allocateur de plus bas niveau, le buddy allocator, se trouve dans le fichier memory.c et la partie "allocation de page" dans page_alloc.c ; la gestion des zones est, quant à elle, présente dans mmzone.c. La couche SLAB, permettant l’allocation via la création de cache et via l’utilisation des primitives kmalloc et kfree se trouve dans slab.c. L’allocation de mémoire non contiguë est implémentée dans le fichier vmalloc.c. La gestion de la mémoire haute se trouve dans highmem.c ; celle des grosses pages mémoire (2 Mo et 4 Mo) dans hugetlb.c. Les fonctionnalités de mapping mémoire sont présentes dans mmap.c, mremap.c, filemap.c (mapping de fichier), fremap.c, mprotect (gestion des protections des mappings) et mlock.c (verrouillage mémoire des mappings). La mémoire partagée est dans shmem.c, le swap dans swap.c, swap_state.c et swapfile.c, et les primitives de libération de pages inutilisées pouvant interagir avec le swap dans vmscan.c. Nous trouvons également l’implémentation de la synchronisation entre la mémoire et les périphériques de stockage (msync.c, pdflush.c, page-writeback.c, readahead.c). Finalement, la plupart des fonctionnalités restantes sont : le reverse mapping (rmap.c), la gestion mémoire lorsque le système s’en retrouve à court (Out of Memory Management, oom_kill.c), le gestionnaire de mémoire rudimentaire utilisé uniquement dans la phase de boot (bootmem.c) et l’infrastructure implémentée pour les architectures ne possédant pas de MMU (Memory Management Unit, nommu.c).
Toutes les abstractions de la couche réseau (sockets, protocole de communication, etc.) se trouvent dans le répertoire net/. Chaque protocole dispose de son propre sous-répertoire pour abriter ses sources et implémente les opérations bas niveau du protocole qui sont utilisées par les primitives de gestion des sockets (socket.c). C’est dans le sous-répertoire core/ que nous trouvons toutes les fonctionnalités génériques du réseau. D’autres sous-répertoires hébergent des sous-systèmes de l’infrastructure du réseau. Notons par exemple, netfilter/ pour la partie firewall et netlink/ pour la communication entre modules noyau et processus résidant en espace utilisateur.
Nous trouvons ensuite l’implémentation des mécanismes de communication inter-processus de type System V (sémaphores, mémoire partagée et file de message) dans le répertoire ipc/, et la bibliothèque C des fonctions standards utilisées par le noyau dans le répertoire lib/.
Nous avons parlé brièvement de la partie du noyau spécifique aux différents types d’architecture se trouvant dans arch/. Un des fichiers les plus importants et présent dans toutes les architectures et implémentant les relations (points d’entrée des appels système) entre l’espace noyau et utilisateur est : arch/[Type d’architecture]/kernel/entry.S. L’autre partie spécifique aux différents types d’architecture se trouve placée dans des fichiers du répertoire include/ (include/asm-[Type d’architecture]), lequel contient l’ensemble de tous les fichiers d’en-tête du corps du noyau.
Nous trouvons d’autres répertoires abritant les sous-systèmes suivants : l’infrastructure du son (sound/), la gestion des périphériques bloc et notamment l’implémentation des ordonnanceurs I/O (block/), l’infrastructure des Linux Security Modules et notamment l’implémentation de SElinux (security/) et, finalement, toutes les fonctionnalités cryptographiques (crypto/).
Le dernier répertoire hébergeant une énorme partie des sources du noyau et dont nous n’avons pas parlé, contient tous les pilotes de périphériques. Il s’agit du répertoire drivers/, lequel possède un sous-répertoire pour chaque type de périphériques (bloc, char, etc.). Notons que l’organisation au sein de ce répertoire est assez "anarchique". Nous trouvons sinon également des sous-répertoires spécifiques aux bus et abritant du code générique pour la gestion des périphériques y étant associés (pci, usb, ieee1394, etc.).
Notre tour d’horizon au sein des sources du noyau prend fin et nous espérons qu’il vous aidera à accéder plus rapidement aux informations nécessaires pour assouvir votre curiosité ou pour commencer à hacker le noyau. Car ne l’oubliez pas, la source d’information la plus fiable se trouve toujours dans le code source ;)

Voyage au cœur de smpnice

Le load balancing avant smpnice

Avant de s’immerger dans smpnice, introduisons brièvement ce qu’est le load balancing. L’ordonnanceur de Linux sur un système multiprocesseur, s’occupe de répartir les différents processus sur l’ensemble des processeurs disponibles (à chacun est associé une runqueue), afin d’équilibrer leur charge. Pour cela, il fait appel à la fonction load_balancing. Cette fonction est appelée régulièrement par la fonction rebalance_tick, elle-même exécutée à chaque tick de l’horloge par la fonction schedule_tick. Notons que load_balancing n’est pas systématiquement exécuté à chaque tick.
Afin d’être efficace, la répartition de charges s’effectue par étape, au sein d’un même domaine d’ordonnancement. Chaque domaine est un ensemble de CPU appartenant au système. Ils sont hiérarchisés : chaque domaine contient un ensemble de groupes qui le partitionnent et qui correspondent aux domaines du niveau inférieur. Chaque domaine possède un lien vers son père. Le domaine de plus haut niveau couvre l’ensemble des processus. Au plus bas de l’échelle, un CPU correspond à un groupe (dans le cas où la technologie HyperThreading est disponible, le plus bas de l’échelle est constitué par les CPU virtuels). Notons que le noyau 2.6.17 introduit un nouveau domaine pour les processeurs multi-cœurs ayant un cache partagé, afin d’effectuer des décisions d’ordonnancement plus pertinentes en regard de la performance.
Prenons l’exemple d’une architecture NUMA à deux nœuds de quatre CPU chacun. Le domaine de plus haut niveau couvre l’ensemble des CPU via deux groupes correspondant aux deux nœuds. Chacun est un domaine contenant quatre groupes, lesquels sont associés à un des CPU du nœud.
Revenons à la fonction rebalance_tick. Elle effectue une itération sur tous les domaines associés au chemin partant du domaine de plus bas niveau contenant le processeur courant, à celui de plus haut niveau. Pour chacun, elle vérifie certaines conditions et appelle load_balancing le cas échéant.
Cette fonction va alors chercher dans le domaine, le groupe le plus chargé (via find_busiest_group). Elle va ensuite récupérer dans le groupe la runqueue du CPU le plus chargé en nombre de processus (via find_busiest_queue). Finalement, elle va essayer de migrer un certain nombre de processus de cette runqueue vers la runqueue du CPU courant (via move_tasks). Si cette opération échoue, le migration thread de la runqueue la plus chargée est réveillé afin d’effectuer la migration lui-même. Notons que si le CPU le plus chargé correspond au CPU courant, la fonction ne fait rien.

Le problème du load balancing sans smpnice

Le load balancing décrit est défaillant pour ce qui est du respect des priorités associées aux processus. Prenons un exemple simple pour comprendre le problème. Soit un système composé de deux processeurs, sur lesquels tournent quatre processus : P1 et P2 de priorité faible (valeur de nice égale à 19), et P3 et P4 de priorité forte (valeur de nice égale à 0). L’ordonnanceur sans le patch smpnice peut équilibrer la charge de façon injuste vis-à-vis des priorités. En effet, seul le nombre de processus est utilisé pour calculer la charge. Par conséquent, la situation où P1 et P2 se retrouve sur un processeur et P3 et P4 sur un autre a une probabilité de se produire de 1/3. Dans une telle configuration, les priorités perçues des processus sont identiques, chacun octroie 50% de CPU. Pour résoudre ce problème, Peter Williams a implémenté une solution simple n’entraînant que peu de modifications, laquelle a été intégrée dans le noyau 2.6.18.

La solution apportée par smpnice

smpnice apporte deux modifications majeures. Il calcule une valeur représentant la charge d’un processus en fonction de sa priorité. Il effectue ensuite ces décisions de répartition de charges sur la valeur du déséquilibre. Prenons un exemple pour comprendre la nécessité de ces deux idées. Considérons cette fois-ci un système à deux processeurs sur lesquels tournent huit processus (tous en état running et "non interactif") : sur l’un quatre de nice 19 et sur l’autre quatre de nice 0. Dans cette configuration, la charge est respectivement de 0,2 pour le premier processeur et de 4,0 pour le second. Le load balancing va alors détecter un déséquilibre de charge et va déplacer deux processus de nice 0 sur le processeur de charge 0,2 pour aboutir à une répartition de 2,0 et 2,2. Si le déséquilibre résiduel dépasse le seuil toléré, alors une nouvelle répartition de charge prend place. Dans ce cas, le choix des processus à déplacer doit se fonder sur le déséquilibre existant, c’est-à-dire ici 0,1. La fonction responsable de la répartition de la charge (move_tasks) va alors choisir de déplacer un processus de nice 19, entraînant une charge égale à 2,1 sur les deux processeurs.
Notons que move_tasks, sans la modification apportée, transfère un nombre de processus donné d’une runqueue à une autre en commençant par ceux de priorité forte. Cela aurait par conséquent induit un déplacement d’un processus de nice 0 sur le processeur de charge 2,0 et aurait abouti à une répartition de 3,0 et 1,2, qui aurait déclenché de nouveau le load balancing, produisant ainsi une boucle infinie. Il est donc nécessaire d’effectuer la décision de répartition de charges sur la valeur du déséquilibre.

Implémentation

Voyons où interviennent les changements principaux. Tout d’abord le champ load_weight a été ajouté aux descripteurs de processus afin d’en conserver la valeur de la charge. Cette consommation supplémentaire de mémoire aboutit à un gain de performance en évitant le calcul systématique de la charge en fonction de la valeur nice.
Les runqueues se voient ajouter également le nouveau champ raw_weighted_load contenant à tout moment la somme des charges des processus qu’elle regroupe dans l’état TASK_RUNNING (cet état est commun aux processus éligibles pour l’accès à la CPU et à celui s’y trouvant actuellement). Cette structure contenait déjà le champ nr_running qui donne à tout moment le nombre de processus dans cet état. Par conséquent, raw_weighted_load est mis à jour à chaque fois que la valeur de nr_running est modifiée.
La fonction find_busiest_group est modifiée. Le calcul de la charge qui ne faisait intervenir que le nombre de processus (dans le groupe) auxquels était associée la valeur de charge fixe SCHED_LOAD_SCALE, prend en compte désormais la charge moyenne par processus dans chaque groupe (cette valeur est calculée à la volée au fur et à mesure que les runqueues sont visitées).
La fonction try_to_wake_up est utilisée pour réveiller un processus et le placer dans une runqueue. Pour effectuer cela, la valeur SCHED_LOAD_SCALE était utilisée pour calculer la moyenne de charge par processus dans une runqueue et ainsi déterminer celle qui hébergerait le processus nouvellement réveillé. Cette moyenne fait maintenant intervenir le champ raw_weighted_load des runqueues.
La fonction move_tasks se voit ajouter le paramètre max_load_move indiquant la charge totale à déplacer d’une runqueue à l’autre. Cette fonction conserve toujours le paramètre max_nr_move signifiant le nombre de processus à déplacer. Nous pouvons nous demander pourquoi avoir garder cet attribut. En fait, une fonction appelée par les migration threads : active_load_balance utilise move_tasks pour déplacer exactement un processus. Il est donc nécessaire de conserver l’argument en question. Une modification de active_load_balance pour ne plus utiliser move_tasks entraînerait une simplification importante de cette dernière.
Finalement, parmi les fonctions principales modifiées, set_user_nice met à jour la valeur du champ load_weight du processus ciblé en plus de son champ nice. Elle modifie également la valeur de raw_weighted_load de la runqueue correspondante.
Quelques subtilités n’ont pas été abordées ici afin de conserver un propos relativement clair. Pour avoir plus de détails, je vous conseille comme toujours de regarder les sources, en l’occurrence il s’agit ici du fichier kernel/sched.c.