Structure interne du noyau Linux 2.4

La source de la dernière version originale (en anglais) de ce guide peut être téléchargée depuis http://www.moses.uklinux.net/patches/lki.sgml. Il est également possible de la lire en ligne à http://www.moses.uklinux.net/patches/lki.html.

Ce guide en version originale est également diffusé par le Projet de documentation Linux (LDP). Il est disponible via ce projet sous différents formats depuis http://www.tldp.org/guides.html.

L'adaptation française de ce guide a été réalisée dans le cadre du projet traduc.org. La dernière version française de ce document est disponible à http://www.traduc.org/docs/guides/lecture/lki/. N'hésitez pas à faire parvenir tout commentaire relatif à cette version à commentaires CHEZ traduc POINT org.

Cette documentation est libre ; vous pouvez la redistribuer ou la modifier dans les conditions de la Licence publique générale GNU (GNU GPL) telle que publiée par la Free Software Foundation; soit selon la version 2 de la licence, ou (à votre choix) une plus récente. (NdT : une version française officieuse de cette licence est disponible à http://www.linux-france.org/article/these/gpl.html).

Remerciements à :

L'adaptation française de ce document a été réalisée par Yaël Gomez <ygomez CHEZ yosins POINT net>. La relecture de ce document a été réalisée par Claire Boussard <clboussard CHEZ free POINT fr>. La publication de ce document a été préparée par Jean-Philippe Guérard <jean TIRET philippe POINT guerard CHEZ laposte POINT net>.

Ce paragraphe décrit les étapes de la compilation d'un noyau Linux et les messages renvoyés à chaque étape. Le processus de construction du noyau dépend de l'architecture, c'est pourquoi je voudrais souligner que l'on ne considérera ici que la compilation d'un noyau Linux/x86.

Quand l'utilisateur tape « make zImage » ou « make bzimage », l'image amorçable du noyau qui en résulte est stockée respectivement en tant que arch/i386/boot/zImage ou arch/i386/boot/bzImage. Voici comment cette image est construite :

La taille d'un secteur d'amorçage est toujours de 512 octets. La taille de setup doit faire plus de 4 secteurs, mais pas plus de 12k — la règle est :

0x4000 octets >= 512 + setup_sects * 512 + la place pour la pile pendant l'exécution de bootsector/setup

On verra plus tard d'où vient cette restriction.

La taille maximum du bzImage produit à cette étape est d'à peu près 2,5M pour amorcer avec LILO et de 0xFFFF (0xFFFF0 = 1048560 octets) pour amorcer avec une image binaire, c.a.d depuis une disquette ou un cédérom (émulation El-Torito).

Remarquez qu'alors que tools/build contrôle la taille du secteur d'amorçage, de l'image du noyau et la limite inférieure de la taille de setup, il ne vérifie pas la taille maximum de setup. Dès lors il est facile de construire un noyau défectueux rien qu'en ajoutant quelques grands espaces (« .space ») à la fin de setup.S.

Les détails du processus d'amorçage sont spécifiques à l'architecture, on va donc s'intéresser à l'architecture IBM PC/IA32. A cause de sa conception vieillissante et du besoin de garder une compatibilité ascendante, le microcode (firmware) des PC démarre le système de manière plutôt démodée. Ce processus peut être divisé en six étapes logiques :

Le secteur d'amorçage (bootsector) utilisé pour démarrer Linux peut être soit :

On va s'intéresser ici en détail au secteur d'amorçage Linux. Les premières lignes initialisent des macros qui seront utilisées comme valeurs de segment :

29 SETUPSECS = 4  	    /* défaut pour le nombre de secteurs de lancement */
30 BOOTSEG   = 0x07C0	    /* adresse originelle du secteur d'amorçage */
31 INITSEG   = DEF_INITSEG  /* nous déplaçons l'amorçage ici — hors du chemin */
32 SETUPSEG  = DEF_SETUPSEG /* le lancement démarre ici */
33 SYSSEG    = DEF_SYSSEG   /* le système est chargé à 0x10000 (65536) */
34 SYSSIZE   = DEF_SYSSIZE  /* taille du système~: # en clicks de 16-octets */

(Les nombres sur la gauche sont les numéros de lignes du fichier bootsect.S). Les valeurs de DEF_INITSEG, DEF_SETUPSEG, DEF_SYSSEG et DEF_SYSSIZE sont tirées de include/asm/boot.h :

/* Ne changez rien ici, sauf si vous savez vraiment ce que vous faites. */
#define DEF_INITSEG     0x9000
#define DEF_SYSSEG      0x1000
#define DEF_SETUPSEG    0x9020
#define DEF_SYSSIZE     0x7F00

Maintenant, regardons le détail du code de bootsect.S :

54     movw    $BOOTSEG, %ax
55     movw    %ax, %ds
56     movw    $INITSEG, %ax
57     movw    %ax, %es
58     movw    $256, %cx
59     subw    %si, %si
60     subw    %di, %di
61     cld
62     rep
63     movsw
64     ljmp    $INITSEG, $go
     
65  # bde — 0xff00 changé en 0x4000 => permet l'accès débogueur > 0x6400(bde).
66  # Ce ne serait pas un soucis si nous avions testé le haut de la mémoire. La
67  # configuration BIOS peut aussi permettre de placer en mémoire haute les tableaux
68  # des disques wini plutôt que dans le tableau des vecteurs. Il est possible
69  # que l'ancienne pile aie corrompu le tableau des disques.

70 go: movw    $0x4000-12, %di  # 0x4000 est une valeur arbitraire >=
71                              # la longueur du secteur d'amorçage
72                              # + la longueur du setup + laplace pour
73                              # la pile ; 12 est la taille du disk parm.
74     movw    %ax, %ds		# ax et es contiennent déjà INITSEG
75     movw    %ax, %ss
76     movw    %di, %sp		# place la pile à INITSEG:0x4000-12.

Les lignes de 53 à 60 déplacent le code du secteur d'amorçage de l'adresse 0x7c00 à 0x9000. Ce qui est fait en :

Si ce code n'utilise pas rep movsd, c'est intentionnel (pensez à .code16).

La ligne 64 saute vers le label go: dans la nouvelle copie du secteur d'amorçage, soit dans le segment 0x9000. Ceci plus les trois instructions suivantes (lignes 64-76) prépare la pile à $INITSEG:0x4000-0xC, i.e. %ss = $INITSEG (0x9000) et %sp = 0x3FF4 (0x4000-0xC). C'est de là que vient la limite sur la taille de setup mentionnée plus haut (voir Construire l'image du noyau Linux).

Les lignes 77-103 corrigent la table des paramètres du disque afin de permettre la lecture multi-secteurs :

77	# La table des paramètres de disque par défaut de nombreux BIOS ne
78	# permet pas la lecture multi-secteurs au-delà du numéro de secteur
79	# maximum spécifié dans le tableau des paramètres par défaut de la
80	# disquette, cela peut signifier 7 secteurs dans certains cas.
81	#
82	# Lire les secteurs un à un est lent et donc hors de question,
83	# nous remédions à cela en créant une table en RAM avec de nouveaux
84	# paramètres (pour le 1er disque). Nous mettons le nb max. de secteurs 
85	# à 36 — nous ne rencontrerons pas plus pour un ED 2.88.  
86	#
87	# Une valeur trop haute ne nuit pas, une trop basse, si.
88	#
89	# Les segments sont comme suit~: ds = es = ss = cs — INITSEG,
90	# fs = 0, et gs est inutilisé.
     
91     movw    %cx, %fs        # met fs à 0
92     movw    $0x78, %bx      # fs:bx est l'adresse du tableau des paramètres
93     pushw   %ds
94     ldsw    %fs:(%bx), %si  # ds:si est la source
95     movb    $6, %cl         # copie 12 octets
96     pushw   %di             # di = 0x4000-12.
97     rep                     # pas besoin de cld -> c'est fait
98     movsw                   # à la ligne 66
99     popw    %di
100    popw    %ds
101    movb    $36, 0x4(%di)   # corrige le compte des secteurs
102    movw    %di, %fs:(%bx)
103    movw    %es, %fs:2(%bx)

Le contrôleur de disquette est réinitialisé en utilisant la fonction 0 du service BIOS int 0x13 et les secteurs de setup sont chargés juste après le secteur d'amorçage, i.e. à l'adresse physique 0x90200 ($INITSEG:0x200), en utilisant encore le service BIOS int 0x13, fonction 2 (lire le(s) secteur(s)). Ça se passe aux lignes 107-124 :

107 load_setup:
108    xorb	%ah, %ah		# reset FDC 
109    xorb	%dl, %dl
110    int 	$0x13	
111    xorw	%dx, %dx           # lecteur 0, tête 0
112    movb	$0x02, %cl         # secteur 2, piste 0
113    movw	$0x0200, %bx       # adresse = 512, dans INITSEG
114    movb	$0x02, %ah         # service 2, « lire secteur(s) »
115    movb	setup_sects, %al   # (suppose que tout est tête 0, piste 0)
116    int	$0x13              # lire
117    jnc	ok_load_setup      # ok — continuons
    
118    pushw	%ax                # sort un code d'erreur
119    call	print_nl
120    movw	%sp, %bp
121    call	print_hex
122    popw	%ax	
123    jmp	load_setup
      
124  ok_load_setup:

Si le chargement échoue pour quelque raison que ce soit (la disquette est abîmée ou quelqu'un a retiré la disquette pendant le chargement), on affiche un code d'erreur et on réessaie de lire dans une boucle infinie. Le seul moyen d'en sortir est de réamorcer la machine, à moins que l'une des tentatives réussisse, mais cela a peu de chances d'arriver (si quelque chose merde, ça ne peut qu'empirer).

Si le chargement des secteurs du code de lancement setup_sect réussit, on saute au label ok_load_setup˜:.

On procède alors au chargement de l'image compressée du noyau à l'adresse physique 0x10000. Ainsi on préserve les zones de données du microcode en mémoire basse (0-64k). Une fois que le noyau est chargé, on saute en $SETUPSEG:0 (arch/i386/boot/setup.S). Lorsqu'on n'a plus besoin des données (i.e. plus d'appel au BIOS), elles sont écrasées en déplaçant le noyau complet (compressé) de 0x10000 vers 0x1000 (ce sont des adresses physiques bien sûr). C'est fait par setup.S qui met les choses en place pour le mode protégé et saute en 0x1000 qui est le début du noyau compressé, i.e. arch/386/boot/compressed/{head.S,misc.c}. Ceci configure la pile puis on appelle decompress_kernel() qui décompresse le noyau a l'adresse 0x10000 et on y saute.

Remarquez que les vieux chargeurs d'amorçage (vieilles versions de LILO) ne pouvaient charger que seulement les 4 premiers secteurs de setup, c'est pourquoi il y a un code dans setup qui charge le reste de lui-même si besoin est. D'autre part, le code de setup devait tenir compte des diverses combinaisons de type/version de chargeur par rapport à zImage/bzImage et est donc très complexe.

Examinons la bidouille (kludge) dans le code du secteur d'amorçage qui nous permet de charger un gros noyau appelé aussi « bzImage ». Les secteurs de setup sont chargés comme d'habitude en 0x90200, mais le noyau est chargé par morceaux de 64k, grâce à une fonction qui appelle le BIOS pour déplacer les données de la mémoire basse vers la mémoire haute. Cette fonction est référencée par bootsect_kludge dans bootsect.S et est définie en tant que bootsect_helper dans setup.S. Le label bootsect_kludge dans setup.S contient la valeur du segment de setup et le décalage du code bootsect_helper par rapport à lui de telle façon que bootsector peut utiliser l'instruction lcall pour y sauter (saut inter-segment). La raison pour laquelle ce code est dans setup.S est simplement qu'il n'y a plus de place dans bootsect.S (ce n'est pas tout à fait exact — il reste approximativement 4 octets et au moins 1 octet de libre dans bootsect.S mais c'est évidemment insuffisant). Cette fonction utilise le service BIOS int 0x15 (ax=0x8700) pour déplacer des données vers la mémoire haute et réinitialise toujours %es afin de pointer sur 0x10000. Ainsi on s'assure que le code de bootsect.S ne sort pas de la mémoire basse lors de la copie des données depuis le disque.

Il y a plusieurs avantages à utiliser un chargeur d'amorçage spécialisé (LILO) par rapport au simple secteur d'amorçage de Linux :

Les vieilles versions de LILO (v17 et avant) ne peuvent pas charger les noyaux bzImage. Les nouvelles versions (depuis quelques années) utilisent les mêmes techniques que bootsect+setup de déplacement des données de la mémoire basse vers la haute par le biais de services BIOS. Quelques personnes (Peter Anvin notamment) pensent que le support de zImage devrait être supprimé. La raison principale pour le conserver (d'après Alan Cox), c'est qu'il reste des BIOS « foireux » qui rendent impossible d'amorcer bzImage alors qu'ils chargent bien zImage.

La dernière chose que fait LILO est de sauter vers setup.S et les choses se déroulent ensuite comme d'habitude.

Par « initialisation de haut niveau » on entend tout ce qui n'est pas directement lié au bootstrap, même si certaines parties du code exécuté sont écrites en assembleur, à savoir arch/i386/kernel/head.S qui est le début du noyau non compressé. Les étapes suivantes sont exécutées :

La init/main.c:start_kernel() est écrite en C et fait les choses suivantes :

La chose importante à noter ici c'est que le thread noyau init() appelle do_basic_setup() qui à son tour appelle do_initcalls() qui parcourt la liste des fonctions enregistrées par le biais de __initcall ou de la macro module_init() et les invoque. Ces fonctions ne dépendent pas les unes des autres ou bien leurs dépendances ont été manuellement fixées par l'ordre de l'édition de liens dans les Makefiles. Ce qui veut dire qu'en fonction de la position des répertoires dans l'arborescence et de la structure des Makefiles, l'ordre dans lequel les fonctions d'initialisation sont appelées peut changer. Quelquefois, c'est important d'en tenir compte car imaginez deux sous-systèmes A et B avec B dépendant d'initialisations faites dans A. Si A est compilé statiquement et que B est un module, alors on est sûr qu'on entrera dans B après que A ait préparé tout l'environnement nécessaire. Si A est un module, alors B en est nécessairement un aussi donc il n'y pas de problème. Mais que se passe-t-il si A et B sont liés statiquement dans le noyau ? L'ordre dans lequel ils sont invoqués dépend du décalage relatif de leurs points d'entrée dans la section ELF .initcall.init de l'image noyau. Rogier Wolff a proposé d'introduire une infrastructure à priorité hiérarchique dans laquelle les modules permettraient à l'éditeur de liens (linker) de savoir dans quel ordre (relatif) ils doivent être liés, mais jusqu'ici il n'y pas de correctif disponible qui implémente cela de manière suffisamment élégante pour être acceptable dans le noyau. Néanmoins assurez vous de l'ordre de liage. Si dans l'exemple ci-dessus A et B marchent bien une première fois en étant compilés statiquement, ils marcheront toujours, pourvu qu'ils soient listés séquentiellement dans le même Makefile. S'ils ne marchent pas, changez l'ordre dans lequel leurs fichiers objets sont listés.

Une autre chose qui vaut d'être notée c'est la capacité qu'a Linux d'exécuter un « autre programme init » en passant une ligne de commande « init= » à l'amorçage. C'est utile pour réparer un /sbin/init abîmé accidentellement ou déboguer les scripts d'initialisation (rc) et /etc/inittab à la main, en les exécutant un par un.

Sur un système multiprocesseur, le processeur d'amorçage (BP) exécute la séquence normale d'instructions du secteur d'amorçage (bootsector), setup etc. jusqu'à ce qu'on atteigne start_kernel(), et ensuite smp_init() et plus particulièrement src/i386/kernel/smpboot.c:smp_boot_cpus(). Le smp_boot_cpus() effectue une boucle pour chaque apicid (jusqu'à NR_CPUS) et appelle pour chacun do_boot_cpu(). Ce que fait do_boot_cpu(), c'est créer (i.e. fork_by_hand) une tâche inactive (idle) pour le cpu cible et écrire à des emplacements bien définis par les spécifications Intel MP (0x467/0x469) l'EIP du code « trampoline » contenu dans trampoline.S. Ensuite il génère STARTUP IPI sur le cpu cible, ce qui fait que cet AP exécute le code de trampoline.S.

Le CPU d'amorçage crée une copie du code de trampoline pour chaque CPU en mémoire basse. Le code AP écrit un nombre magique dans son propre code qui est vérifié par le processeur d'amorçage pour s'assurer que l'AP est en train d'exécuter le code trampoline. La nécessité de mettre le code trampoline en mémoire basse vient des spécifications Intel MP.

Le code trampoline met simplement le registre %bx à 1, passe en mode protégé et saute vers startup_32 qui est l'entrée principale de arch/i386/kernel/head.S.

Maintenant que l'AP a commencé l'exécution de head.S et découvre que ce n'est pas un processeur d'amorçage, il passe le code qui nettoie la BSS et appelle initialize_secondary() qui ne fait qu'appeler la tâche inactive pour ce CPU — rappelez vous que init_tasks[cpu] avait déjà été initialisé par le processeur d'amorçage en exécutant do_boot_cpu(cpu).

Remarquez que init_task peut être partagé mais que chaque tâche inactive doit avoir sa propre TSS. C'est pourquoi init_tss[NR_CPUS] est un tableau.

Une fois que le système d'exploitation s'est initialisé, la plus grande partie du code et des structures de données ne sont jamais réutilisés. La plupart des systèmes (BSD, FreeBSD etc.) ne peuvent disposer de ces informations, et donc gaspillent la précieuse mémoire physique du noyau. L'excuse qu'ils fournissent (voir le livre McKusick's 4.4BSD) c'est que le code en question est réparti autour de plusieurs sous-systèmes et que ce n'est pas faisable de le libérer : the relevant code is spread around various subsystems and so it is not feasible to free it. Linux, bien sûr, ne peut se retrancher derrière de telles excuses car sous Linux « si quelque chose est en principe possible, alors c'est déjà implémenté ou quelqu'un travaille dessus ».

Donc, comme je l'ai dit plus tôt, le noyau Linux ne peut être compilé que comme un binaire ELF, et maintenant nous en avons la raison (ou une des raisons). La raison rattachée à l'élimination des données et du code d'initialisation est que Linux fournit 2 macros à utiliser :

Elles s'évaluent comme des spécificateurs d'attributs gcc (aussi connus comme « gcc magic ») telles que définies dans include/linux/init.h :

#ifndef MODULE
#define __init        __attribute__ ((__section__ (".text.init")))
#define __initdata    __attribute__ ((__section__ (".data.init")))
#else
#define __init
#define __initdata
#endif

Ce qui veut dire que si le code est compilé statiquement dans le noyau (i.e on ne définit pas MODULE), alors celui ci est placé dans une section ELF spéciale .text.init, qui est déclarée dans la carte de correspondance de l'éditeur de lien dans arch/i386/vmlinux.lds. Sinon (i.e. si c'est un module) les macros sont évaluées à rien.

Ce qui ce passe durant l'amorçage, c'est que le thread noyau « init » (fonction init/main.c:init()) appelle une fonction spécifique à l'architecture free_initmem() qui libère toutes les pages entre les adresses __init_begin et __init_end.

Sur un système typique (ma station de travail), le résultat est que 260k de mémoire sont libérés.

Les fonctions enregistrées via module_init() sont placées dans .initcall.init qui est aussi libéré lors d'une compilation statique. La tendance actuelle sous Linux, quand on crée un sous-système (pas forcement un module), est de fournir dès les premières étapes de la conception les points d'entrée init/exit de telle façon que le sous-système puisse dans le futur être modularisé si besoin. Pipefs en est un exemple, regardez fs/pipe.c. Même si un sous système donné ne doit jamais devenir un module, i.e. bdflush (voir fs/buffer.c), c'est toujours mieux et plus propre d'utiliser la macro module_init() à la place de la fonction d'initialisation, pourvu qu'on n'attache pas d'importance au moment exact où la fonction est appelée.

Il y a deux autres macros qui fonctionnent de manière similaire, appelées __exit et __exitdata, mais elles sont plus directement liées au support des modules et par conséquent seront expliquées dans un prochain paragraphe.

Rappelons nous ce que devient la ligne de commande passée au noyau pendant l'amorçage :

Alors, comment écrit-on le code qui traite la ligne de commande d'amorçage ? On utilise la macro __setup() définie dans include/linux/init.h :

/*
 * Utilisé pour initialiser les paramètres du noyau avec les valeurs
 * de la ligne de commande
 */
struct kernel_param {
const char *str;
int (*setup_func)(char *);
};

extern struct kernel_param __setup_start, __setup_end;
#ifndef MODULE
#define __setup(str, fn) \
static char __setup_str_##fn[] __initdata = str; \
static struct kernel_param __setup_##fn __initsetup = \
	      { __setup_str_##fn, fn }

#else
#define __setup(str,func) /* rien */
#endif

Alors, typiquement vous l'utiliserez dans votre code de la façon suivante (pris du code d'un vrai driver, BusLogic HBA drivers/scsi/BusLogic.c :

static int __init
BusLogic_Setup(char *str)
{
int ints[3];
	      
(void)get_options(str, ARRAY_SIZE(ints), ints);
     
if (ints[0] != 0) {
    BusLogic_Error("BusLogic: Obsolete Command Line Entry "
   "Format Ignored\n", NULL);
   return 0;
   }
if (str == NULL || *str == '\0')
   return 0;
   return BusLogic_ParseDriverOptions(str);
   }
	      
__setup("BusLogic=", BusLogic_Setup);

Remarquez que __setup() ne fait rien pour les modules, donc le code qui veut traiter la ligne de commande d'amorçage et qui peut être soit dans un module, soit lié statiquement doit invoquer sa fonction d'analyse syntaxique manuellement dans la routine d'initialisation du module. Ce qui veut aussi dire qu'il est possible d'écrire du code qui est capable de traiter les paramètres quand il est compilé comme un module et pas quand il est statique ou vice versa.

Sous Linux une structure struct task_struct est allouée dynamiquement à chaque processus. Le nombre maximum de processus qui peuvent être crées sous Linux est limité par la quantité de mémoire physique présente, et est égal à (voir kernel/fork.c:fork_init() :

/*
* La valeur par défaut du nombre maximum de threads est fixée à une
* valeur sûre~: la structure des threads peut occuper au maximum la moitié
* de la mémoire.
*/
max_threads = mempages / (THREAD_SIZE/PAGE_SIZE) / 2;

ce qui, sur une architecture IA32, veut dire num_physpages/4. Par exemple, sur une machine de 512 M, vous pouvez créer 32k de threads. C'est une amélioration considérable par rapport à la limite 4k-epsilon des vieux noyaux (2.2 et avant). De plus, cela peut-être modifié soit pendant l'exécution en utilisant KERN_MAX_THREADS de sysctl(2), soit simplement en utilisant l'interface procfs pour paramétrer le noyau :

# cat /proc/sys/kernel/threads-max 
32764
# echo 100000 > /proc/sys/kernel/threads-max 
# cat /proc/sys/kernel/threads-max 
100000
# gdb -q vmlinux /proc/kcore
Core was generated by `BOOT_IMAGE=240ac18 ro root=306 video=matrox:vesa:0x118'.
#0  0x0 in ?? ()
(gdb) p max_threads
$1 = 100000

L'ensemble des processus sur un système Linux est représenté par un ensemble de structures struct task_struct qui sont liées de deux façons :

La table de hachage est appelée pidhash[] et est définie dans include/linux/sched.h :

/* Hachage sur le PID. (est-ce que ceci ne devrait pas être dynamique~?) */
#define PIDHASH_SZ (4096 >> 2)
extern struct task_struct *pidhash[PIDHASH_SZ];
     
#define pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

Les tâches sont hachées en fonction de leur pid et la fonction précédente est censée distribuer les éléments uniformément dans leur domaine (de 0 à PID_MAX-1). La table de hachage est utilisée pour retrouver rapidement une tâche par son pid en utilisant find_task_pid() in-line depuis include/linux/sched.h :

static inline struct task_struct *find_task_by_pid(int pid)
{
struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];
  
for(p = *htable; p && p->pid != pid; p = p->pidhash_next);
 
return p;
}

Les tâches de chaque liste de hachage (i.e hachées à la même valeur) sont liées par p->pidhash_next/pidhash_pprev qui sont utilisés par hash_pid() et unhash_pid() pour insérer et retirer un processus donné dans la table de hachage. Ceci est fait sous la protection d'un verrou tournant en lecture/écriture (read/write spinlock) appelé tasklist_lock posé pour ÉCRIRE (WRITE).

La double liste chaînée circulaire qui utilise p->next_task/prev_task est tenue à jour de façon à ce que l'on puisse parcourir toutes les tâches du système facilement. C'est fait par la macro for_each_task() de include/linux/sched.h :

#define for_each_task(p) \
for (p = &init_task ; (p = p->next_task) != &init_task ; )

Les utilisateurs de for_each_task() doivent poser un verrou tasklist_lock pour LIRE. Remarquez que for_each_task() utilise init_task pour marquer le début et la fin de la liste — c'est plus sûr car la tâche inactive (idle — pid 0) ne finit jamais.

Les fonctions qui modifient la table de hachage des processus ou des liens de la table des processus, notamment fork(), exit() et ptrace(), doivent poser tasklist_lock pour ÉCRIRE. Ce qui est plus intéressant, c'est que pour écrire il faut aussi désactiver les interruptions sur le CPU local. La raison de cela est loin d'être triviale : la fonction send_sigio() parcourt la liste des tâches et donc pose un tasklist_lock pour LIRE, et elle est appelée depuis kill_fasync() dans un contexte d'interruption. C'est pourquoi ceux qui écrivent doivent désactiver les interruptions alors que ceux qui lisent n'ont pas besoin de le faire.

Maintenant que nous comprenons comment les structures task_struct sont liées ensemble, examinons les membres de task_struct. Ils correspondent plus ou moins aux membres des structures UNIX « struct proc » et « struct user » combinées ensemble.

Les autres versions d'UNIX séparaient l'information sur l'état des tâches en une partie qui devait être gardée en mémoire tout le temps (appelée « proc struct » qui inclut l'état du processus, les informations d'ordonnancement etc.) et une autre partie qui n'est nécessaire que lorsque le processus tourne (appelée « u area » qui inclut la table des descripteurs de fichiers, les informations de quota disque etc.). La seule raison d'être d'une conception aussi laide est que la mémoire était alors une denrée rare. Les systèmes d'exploitation modernes (bon, seulement Linux pour le moment mais d'autres, comme FreeBSD semblent évoluer dans la même direction) n'ont pas besoin d'une telle séparation, ils maintiennent l'état des processus dans une structure de données du noyau qui réside en mémoire en permanence.

La structure task_struct est déclarée dans include/linux/sched.h et a actuellement une taille de 1680 octets.

Le champ state (état) est déclaré comme :

volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */

#define TASK_RUNNING            0
#define TASK_INTERRUPTIBLE      1

#define TASK_UNINTERRUPTIBLE    2
#define TASK_ZOMBIE             4
#define TASK_STOPPED            8
#define TASK_EXCLUSIVE          32

Pourquoi est ce que TASK_EXCLUSIVE est définie comme 32 et non 16 ? parce que 16 était utilisé par TASK_SWAPPING et que j'ai oublié de décaler TASK_EXCLUSIVE quand j'ai retiré toutes les références à TASK_SWAPPING (quelquefois dans 2.3.x).

La déclaration volatile dans p->state signifie qu'il peut être modifié de manière asynchrone (depuis un gestionnaire d'interruption) :

Les drapeaux (flags) de tâches contiennent des informations sur les états des processus, états qui ne sont pas mutuellement exclusifs :

unsigned long flags;  /* drapeaux pour chaque processus, cf. plus bas */
/*
 * Drapeaux par processus
 */
#define PF_ALIGNWARN  0x00000001    /* Averti des pb d'alignement. Pas encore */
                                    /* implanté, pour 486 seulement */
#define PF_STARTING   0x00000002    /* en création */
#define PF_EXITING    0x00000004    /* en train de s'arrêter */
#define PF_FORKNOEXEC 0x00000040    /* s'est scindé, mais n'a pas encore */
                                    /* fait de « exec  » */
#define PF_SUPERPRIV  0x00000100    /* a utilisé les privilèges de */
                                    /* super-utilisateur */
#define PF_DUMPCORE   0x00000200    /* a laissé un « core dump » */
#define PF_SIGNALED   0x00000400    /* tué par un signal */
#define PF_MEMALLOC   0x00000800    /* en train d'allouer de la mémoire */
#define PF_VFORK      0x00001000    /* réveille le parent dans mm_release */
#define PF_USEDFPU    0x00100000    /* à util. le FPU au cours de ce */
                                    /* quantième (SMP) */

Les champs p->has_cpu, p->processor, p->counter, p->priority, p->policy et p->rt_priority concernent l'ordonnanceur et seront examinés plus tard.

Les champs p->mm et p->active_mm pointent respectivement sur l'espace d'adressage des processus décrit par la structure mm_struct et vers l'espace d'adressage actif si le processus n'en n'a pas un réel (i.e. pour les threads noyau). Cela aide à minimiser les débordements de TLB lors d'un basculement d'espace d'adressage quand une tâche est sortie de l'ordonnancement. Donc, si on ajoute une tâche dans l'ordonnanceur (qui n'a pas de p->mm) alors son next->active_mm sera positionné sur le prev->active_mm de la tâche qui est sortie, qui sera le même que prev->mm si prev->mm != NULL. L'espace d'adressage peut être partagé entre les threads si le drapeau (flag) CLONE_VM est passé à l'appel système clone(2) ou par le biais de l'appel système vfork(2).

Les champs p->exec_domain et p->personality sont liés à la personnalité de la tâche, i.e. la façon dont certain appels système se comportent pour émuler la « personnalité » de certaines versions éloignées d'UNIX.

Le champs p->fs contient les informations sur le système de fichiers, ce qui veut dire sous Linux 3 types d'informations :

Cette structure inclut aussi un compteur de références car elle peut être partagée entre des tâches clonées quand le drapeau CLONE_FS est passé à l'appel système clone(2).

Le champ p->files contient la table des descripteurs de fichiers. Elle aussi peut être partagée entre des tâches clonées, pourvu que le drapeau CLONE_FILES soit spécifié avec l'appel système clone(2).

le champ p->sig contient les gestionnaires (handlers) de signaux et peuvent être partagés entre des tâches par le biais de CLONE_SIGHAND.

Les livres consacrés aux systèmes d'exploitation définissent les « processus » de différentes façons, depuis « l'instance d'un programme en exécution » jusqu'à « ce qui est produit par les appels système clone(2) ou fork(2) ». Sous Linux il y a trois type de processus :

Le thread inactif est créé à la compilation pour le premier CPU ; il est ensuite crée « manuellement » pour chaque CPU par le biais de la fonction spécifique à l'architecture fork_by_hand() dans arch/i386/kernel/smpboot.c, qui utilise l'appel système fork(2) appelé à la main (sur certaines architectures). Les tâches inactives partagent une structure init_task mais possèdent une structure TSS privée, dans le tableau init_tss de chaque CPU. Les tâches inactives ont toutes un pid = 0 et aucune autre tâche ne peut partager le même pid, i.e. utiliser le drapeau CLONE_PID de clone(2).

Les threads noyau sont créés en utilisant la fonction kernel_thread() qui invoque l'appel système clone(2) en mode noyau. Les threads noyau n'ont pas en général d'espace d'adressage utilisateur, i.e. p->mm = NULL, car il font un exit_mm() explicite, i.e. via la fonction daemonize(). Les threads noyau peuvent toujours accéder directement à l'espace d'adressage du noyau. Il leur est attribué des numéros de pid dans la tranche basse. L'exécution dans l'anneau (ring) 0 du processeur (sur x86, c'est le cas) implique que le thread noyau profite de tous les privilèges d'entrée/sortie et ne peut être préempté par l'ordonnanceur.

Les tâches utilisateurs sont créés avec les appels système clone(2) ou fork(2), qui utilisent la fonction kernel/fork.c:do_fork().

Voyons ce qui se passe quand un processus utilisateur fait un appel système fork(2). Bien que fork(2) soit dépendant de l'architecture à cause des différentes façons de transmettre la pile et les registres utilisateur, la fonction utilisée réellement do_fork() pour ce travail est portable et est placée dans kernel/fork.c.

Les actions suivantes sont réalisées :

Donc les tâches sont créées. Il y a plusieurs façons pour une tâche de se terminer :

Les fonctions implémentant les appels systèmes sous Linux sont préfixées par sys_, mais elles ne font en général que vérifier les arguments ou passer des informations de la façon spécifique à l'architecture et le travail effectif est réalisé par les fonctions do_. Il en est ainsi avec sys_exit() qui appelle do_exit() pour faire le travail. Malgré cela, d'autres parties du noyau invoquent parfois sys_exit() alors quelles devraient plutôt appeler do_exit().

La fonction do_exit() se trouve dans kernel/exit.c. Les points remarquables de do_exit() sont qu'elle :

Le travail de l'ordonnanceur est de répartir l'accès au CPU entre les différents processus. L'ordonnanceur (ou scheduler) est implémenté dans le « fichier main du noyau » kernel/sched.c. Le fichier d'en-tête correspondant include/linux/sched.h est inclus (explicitement ou non) dans à peu près tous les fichiers sources du noyau.

Les champs de la structure de tâche intéressants pour l'ordonnanceur incluent :

L'algorithme de d'ordonnancement est simple, malgré l'apparente complexité de la fonction schedule(). Cette fonction est complexe car elle implémente les trois algorithmes d'ordonnancement en un seul et aussi à  cause de certaines spécificités subtiles de l'architecture multiprocesseur (SMP).

Les gotos apparemment « inutiles » de schedule() sont ici dans le but de générer le code le mieux optimisé (pour i386). Remarquez que le code de l'ordonnanceur (comme la plus grande partie du noyau) a été complètement réécrit pour le 2.4, donc la discussion qui suit ne s'applique pas à  la série des 2.2 ou moins.

Regardons cette fonction en détail :

Avant d'examiner l'implémentation des files d'attentes, nous devons nous familiariser avec l'implémentation standard des doubles listes chaînées de Linux. Les files d'attentes (comme beaucoup d'autres choses dans Linux) en font une utilisation importante et elles sont appelées dans le jargon « implémentation list.h » car le fichier le plus significatif est include/linux/list.h.

La structure de données fondamentale ici est struct list_head :

struct list_head {
    struct list_head *next, *prev;
    };

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
        (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

#define list_entry(ptr, type, member) \
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

Les trois premières macros sont utilisées pour initialiser une liste vide en faisant pointer next et prev sur elle même. Les restrictions syntaxiques du C rendent évidentes les conditions de leur utilisation — par exemple, LIST_HEAD_INIT() peut être utilisée pour l'initialisation des éléments de la structure lors de sa déclaration, la seconde peut être utilisée pour l'initialisation d'une variable statique et la troisième peut être utilisée dans une fonction.

La macro list_entry() donne accès aux éléments individuels de la liste, par exemple (dans fs/file_table.c:fs_may_remount_ro()) :

struct super_block {
   ...
   struct list_head s_files;
   ...
} *sb = &some_super_block;

struct file {
   ...
   struct list_head f_list;
   ...
} *file;

struct list_head *p;

for (p = sb->s_files.next; p != &sb->s_files; p = p->next) {
     struct file *file = list_entry(p, struct file, f_list);
     do something to 'file'
}

Un bon exemple de l'utilisation de la macro list_for_each() se trouve dans l'ordonnanceur quand on parcourt la queue d'exécution en cherchant le processus de meilleure qualité :

static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;

list_for_each(tmp, &runqueue_head) {
    p = list_entry(tmp, struct task_struct, run_list);
    if (can_schedule(p)) {
        int weight = goodness(p, this_cpu, prev->active_mm);
        if (weight > c)
            c = weight, next = p;
    }
}

Ici, p->run_list est déclaré comme struct list_head run_list dans la structure task_struct et sert d'ancrage à  la liste. Le retrait ou l'ajout d'un élément à la liste (au début ou à  la fin de la liste) est fait par les macros list_del()/list_add()/list_add_tail(). Les exemples ci-dessous ajoutent et retirent des tâches à  la file d'exécution :

static inline void del_from_runqueue(struct task_struct * p)
{
        nr_running--;
        list_del(&p->run_list);
        p->run_list.next = NULL;
}

static inline void add_to_runqueue(struct task_struct * p)
{
        list_add(&p->run_list, &runqueue_head);
        nr_running++;
}

static inline void move_last_runqueue(struct task_struct * p)
{
        list_del(&p->run_list);
        list_add_tail(&p->run_list, &runqueue_head);
}

static inline void move_first_runqueue(struct task_struct * p)
{
        list_del(&p->run_list);
        list_add(&p->run_list, &runqueue_head);
}

Quand un processus demande au noyau de faire quelque chose qui n'est pas possible pour l'instant mais qui le sera plus tard, le processus est endormi et il est réveillé à un moment où la requête a plus de chances d'être satisfaite. L'un des mécanismes utilisés pour réaliser cela est appelé « file d'attente (wait queue) ».

L'implémentation Linux autorise le réveil sémantique en utilisant le drapeau TASK_EXCLUSIVE. Avec les files d'attentes, vous pouvez utiliser soit des files bien connues et leurs fonctions sleep_on / sleep_on_timeout / interruptible_sleep_on / interruptible_sleep_on_timeout, ou définir votre propre file d'attente et utiliser add/remove_wait_queue pour ajouter et supprimer des tâches vous même et wake_up/wake_up_interruptible pour les réveiller lorsque c'est nécessaire.

Un exemple du premier usage des files d'attentes est l'interaction entre l'allocateur de pages (dans mm/page_alloc.c:__alloc_pages()) et le démon noyau kswapd (dans mm/vmscan.c:kswap()), par le biais de la file d'attente kswapd_wait, déclarée dans mm/vmscan.c; le démon kswapd dort dans cette file, et il est réveillé à  chaque fois que l'allocateur de pages a besoin de libérer des pages.

Un exemple d'utilisation d'une file d'attente autonome est l'interaction entre un processus utilisateur demandant des données via l'appel système read(2) et le noyau tournant dans un contexte d'interruption pour fournir les données. Le gestionnaire d'interruption peut ressembler à  (drivers/char/rtc_interrupt() simplifié) :

static DECLARE_WAIT_QUEUE_HEAD(rtc_wait);

void rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
	spin_lock(&rtc_lock);	
	rtc_irq_data = CMOS_READ(RTC_INTR_FLAGS);
	spin_unlock(&rtc_lock);	
	wake_up_interruptible(&rtc_wait);
}

Alors, le gestionnaire d'interruption obtient les données en lisant un port d'entrée/sortie spécifique au périphérique (la macroCMOS_READ() réalise quelques instructions outb/inb) puis réveille tous ceux qui dorment dans la file d'attente rtc_wait.

Maintenant, l'appel système read(2) peut être implémenté comme :

ssize_t rtc_read(struct file file, char *buf, size_t count, loff_t *ppos)
{
	DECLARE_WAITQUEUE(wait, current);
	unsigned long data;
	ssize_t retval;

	add_wait_queue(&rtc_wait, &wait);
	current->state = TASK_INTERRUPTIBLE;
	do {
		spin_lock_irq(&rtc_lock);
		data = rtc_irq_data;
		rtc_irq_data = 0;
		spin_unlock_irq(&rtc_lock);

		if (data != 0)
			break;

		if (file->f_flags & O_NONBLOCK) {
			retval = -EAGAIN;
			goto out;

		}
		if (signal_pending(current)) {
			retval = -ERESTARTSYS;
			goto out;
		}
		schedule();
	} while(1);
	retval = put_user(data, (unsigned long *)buf);	
	if (!retval)
		retval = sizeof(unsigned long);

out:
	current->state = TASK_RUNNING;
	remove_wait_queue(&rtc_wait, &wait);
	return retval;
}

Ce qui se passe dans rtc_read() est :

Il vaut la peine de remarquer que l'utilisation des files d'attente rend plus facile d'implémenter l'appel système poll(2) :

static unsigned int rtc_poll(struct file *file, poll_table *wait)
{
        unsigned long l;

        poll_wait(file, &rtc_wait, wait);

        spin_lock_irq(&rtc_lock);
        l = rtc_irq_data;
        spin_unlock_irq(&rtc_lock);


        if (l != 0)
                return POLLIN | POLLRDNORM;
        return 0;
}

Tout le travail est fait par la fonction indépendante du matériel poll_wait() qui fait les manipulations nécessaires sur la file d'attente; il suffit de la faire pointer sur la file d'attente qui est réveillée par notre gestionnaire d'interruption spécifique au périphérique.

Maintenant portons notre attention sur les chronomètres du noyau. Ils sont utilisés pour reporter l'exécution d'une fonction particulière (appelée « timer handler ») à  un instant donné dans le futur. La principale structure de données est struct timer_list déclarée dans include/linux/timer.h :

struct timer_list {
        struct list_head list;
        unsigned long expires;
        unsigned long data;
        void (*function)(unsigned long);
        volatile int running;
};

Le champ list sert à  s'ancrer à  la liste, en étant protégé par le verrou tournant timerlist_lock. Le champ expires est la valeur de jiffies qui provoque l'invocation de function avec le paramètre data. Le champ running est utilisé sur les multiprocesseurs pour tester si le « timer handler » est exécuté par un autre CPU.

Les fonctions add_timer() et del_timer() ajoutent et enlèvent un chronomètre donné à  la liste. Quand un chronomètre expire, il est retiré automatiquement. Avant d'être utilisé, un chronomètre DOIT être initialisé par le biais de la fonction init_timer(). Et avant qu'il soit ajouté, les champs function et expires doivent être positionnés.

Il est parfois raisonnable de séparer l'ensemble de ce qui doit être fait par le gestionnaire d'interruption en travail immédiat (i.e. acquitter l'interruption, mettre à jour les statistiques, et cætera) et en travail qui peut être remis à  plus tard, pendant que les interruptions seront actives (i.e. faire des pré-traitements sur les données, réveiller les processus pour ces données, et cætera).

Les Bottom halves sont un vieux mécanisme pour différer l'exécution de tâches du noyau et elles existent depuis Linux 1.x. Dans Linux 2.0, un nouveau mécanisme a été ajouté, appelé « task queues », qui sera le sujet du prochain paragraphe.

Les Bottom halves sont sérialisées par le verrou tournant global_bh_lock, ce qui veut dire qu'il ne peut y avoir qu'un seul bottom half en exécution sur n'importe quel CPU à  un instant donné. Cependant quand on essaie d'exécuter le gestionnaire, si global_bh_lock n'est pas disponible, le bottom half est marqué (i.e. ordonnancé) pour l'exécution — donc le traitement peut continuer, au contraire d'une boucle tournant sur global_bh_lock.

Il ne peut y avoir au total que 32 bottom halves enregistrés. Les fonctions nécessaires à  la manipulation des bottom halves sont comme suit (toutes exportées dans les modules) :

Les Bottom halves sont des mini-tâches (tasklets) verrouillées globalement, donc la question « quand les routines bottom half sont-elles exécutées ? », se ramène à  « quand les mini-tâches sont-elles exécutées ? ». Et la réponse est, à  deux endroits : a) à chaque schedule() et b) à  chaque chemin de retour d'interruption/appel système dans entry.S (À FAIRE : par conséquent, le cas schedule() est vraiment embêtant — c'est comme ajouter une autre interruption très très lente, pourquoi ne pas se débarrasser du label handle_softirq de schedule() ?).

Les files de tâches peuvent être vues comme l'extension dynamique des vieux bottom halves. En fait, dans le code source elles sont parfois référencées comme « nouveaux » bottom halves. Plus précisément, les vieux bottom halves dont on a discuté dans les section précédentes ont les limitations suivantes :

Par contre, avec les files de tâches, un nombre arbitraire de fonctions peuvent être chaînées et exécutées les unes après les autres ultérieurement. On crée une nouvelle file de tâches en utilisant la macro DECLARE_TASK_QUEUE() et on y ajoute une tâche au moyen de la fonction queue_task(). La file de tâches peut alors être traitée en utilisant run_task_queue(). Au lieu de créer votre propre file de tâches (que vous devrez gérer manuellement), vous pouvez utiliser les files de tâches prédéfinies de Linux qui sont traitées à  des moments bien précis :

A moins que le pilote utilise sa propre liste de tâches, il n'a pas besoin d'appeler run_tasks_queues() pour traiter la file, sauf dans les circonstances expliquées ci-dessous.

La raison pour laquelle les files de tâches tq_timer/tq_scheduler ne sont pas traitées seulement aux endroits habituels mais aussi ailleurs (la fermeture d'un périphérique tty en est un exemple) devient claire si on se rappelle que le pilote peut ordonnancer les tâches dans la file, et que ces tâches n'ont un sens que pendant qu'une instance particulière du périphérique reste valide — généralement jusqu'à  ce que l'application le ferme. Donc, le pilote peut avoir besoin d'appeler run_task_queue() pour évacuer les tâches (et n'importe quoi d'autre) qu'il a mises dans la file, parce que les autoriser à  s'exécuter plus tard n'aurait aucun sens — i.e. les structures de données utiles auraient été libérées/réutilisées par une instance différente. C'est la raison pour laquelle on voit run_task_queue() s'appliquer à  tq_timer et tq_scheduler à  d'autres endroits qu'une interruption de chronomètre et que schedule() respectivement.

Pas encore, dans une révision future.

Pas encore, dans une révision future.

Il y a deux mécanismes sous Linux pour les implémenter :

Les programmes Linux natifs utilisent int 0x80 alors que les binaires d'autres UNIX (Solaris, UnixWare 7, et cætera) utilisent le mécanisme lcall7. Le nom historique « lcall7 » est inexact car il couvre aussi lcall27 (i.e. Solaris/x86), tandis que la fonction de prise en charge est appelée lcall7_func.

Quand le système démarre, la fonction arch/i386/kernel/traps.c:trap_init() est appelée pour configurer l'IDT de façon à  ce que le vecteur 0x80 (de type 15, dpl 3) pointe à  l'adresse d'entrée de system_call dans arch/i386/kernel/entry.S.

Quand une application dans l'espace utilisateur fait un appel système, les arguments sont passés via le registre et l'application exécute l'instruction « int 0x80 ». Ce qui provoque une trappe (trap) dans le mode noyau et le processeur saute au point d'entrée system_call dans entry.S. Voici ce qu'il fait :

Linux supporte jusqu'à  6 arguments pour les appels système. Ils sont passés dans %ebx, %ecx, %edx, %esi, %edi (et %ebp utilisé temporairement, voir _syscall6() dans asm-i386/unistd.h). Le numéro de l'appel système est passé via %eax.

Il y a deux types d'opérations atomiques : bitmaps et atomic_t. Les bitmaps sont très pratiques pour maintenir le concept d'unités « allouées » ou « libres » pour de grands ensembles de données où chaque unité est identifiée par un nombre, par exemple les inodes libres ou les blocs libres. Ils sont aussi largement utilisés pour des verrouillages simples, par exemple pour fournir un accès exclusif à  un périphérique ouvert. Un exemple de ceci peut être trouvé dans arch/i386/kernel/microcode.c :

/*
 *  Nb de bits dans microcode_status. (31 bits de plus pour le futur)
 */
#define MICROCODE_IS_OPEN  0  /* positionné lorsque le périphérique */
                              /* est utilisé */

static unsigned long microcode_status;

Il n'est pas nécessaire d'initialiser micro-code_status à  0 car la BSS est systématiquement remise à  zéro sous Linux.

/*
 * Nous n'autorisons ici qu'un seul utilisateur à la fois pour ouvrir/fermer.
 */
static int microcode_open(struct inode *inode, struct file *file)
{
        if (!capable(CAP_SYS_RAWIO))
                return -EPERM;

        /* one at a time, please */
        if (test_and_set_bit(MICROCODE_IS_OPEN, &microcode_status))
                return -EBUSY;

        MOD_INC_USE_COUNT;
        return 0;
}

Les opérations sur les bitmaps sont :

Ces opérations utilisent la macro LOCK_PREFIX, qui s'évalue au préfixe de l'instruction de verrouillage du bus (lock) sur les noyaux multiprocesseur et à  rien sur de l'uniprocesseur. Ce qui garantit l'atomicité de l'accès dans les environnements multiprocesseurs.

Parfois les manipulations de bits ne sont pas pratiques, on aimerait mieux utiliser des opérations arithmétiques — addition, soustraction, incrémentation, décrémentation. Un cas typique en est les compteurs de références (i.e. pour les inodes). Cette facilité est fournie par le type de donnée atomic_t et les opérations suivantes :

Depuis les premiers jours du support Linux (début des années 90s), les développeurs ont été confrontés au classique problème de l'accès à  des données partagées entre différents types de contextes (processus utilisateur vs interruption) et les différentes instances d'un même contexte sur plusieurs CPU.

Le support multiprocesseur et à  rien sur de l'UP. Ce qui garantit l'atomicité a été ajouté à  Linux 1.3.42 le 15 Novembre 1995 (le patch original avait été fait en octobre de la même année).

Si une région de code critique peut être exécutée soit dans un contexte de processus soit dans un contexte d'interruption, alors la façon de le protéger sur de l'UP est d'utiliser les instructions cli/sti :

unsigned long flags;

save_flags(flags);
cli();
/* critical code */
restore_flags(flags);

Tandis que cela marche très bien sur de l'UP, ce n'est bien évidement d'aucune utilité sur du multiprocesseur et à  rien sur de l'UP. Ce qui garantit l'atomicité car la même séquence de code peut être exécutée simultanément sur un autre processeur, et pendant que cli() fournit une protection contre des accès concurrents avec un contexte d'interruption sur chaque CPU individuellement, elle ne fournit pas de protection du tout contre la concurrence entre contextes sur des CPU différents. C'est là  que les verrous tournants sont utiles.

Ils y a trois types de verrous tournants (spinlocks) : basique (vanilla), lecture-écriture (read-write) et gros-lecteur (big-reader). Les verrous tournants en lecture-écriture doivent être utilisés quand il y a une tendance naturelle à  avoir « beaucoup de lecteurs et peu d'écrivains ». Un exemple de ceci est l'accès à  la liste des systèmes de fichiers enregistrés (voir fs/super.c). Cette liste est gardée par file_systems_lock, un verrou tournant en lecture-écriture parce qu'on a besoin d'un accès exclusif quand on enregistre/dés-enregistre un système de fichiers, mais n'importe quel processus peut lire le fichier /proc/filesystems ou utiliser l'appel système sysfs(2) pour forcer un examen systématique en lecture seule de la liste des systèmes de fichiers. C'est là  que l'utilisation des verrous tournant en lecture-écriture prend tout son sens. Avec un verrou tournant en lecture-écriture, on peut avoir plusieurs lecteurs en même temps mais un seul écrivain et il ne peut pas y avoir de lecteurs quand il y a un écrivain. En passant, se serait bien si les nouveaux lecteurs n'obtenaient pas de verrous pendant qu'un écrivain essaie d'en poser un, i.e. si Linux pouvait gérer correctement le problème de la frustration éventuelle d'un écrivain par plusieurs lecteurs. Il faudrait pour cela que les lecteurs soient bloqués pendant qu'un écrivain essaie de poser un verrou. Ce n'est pas le cas actuellement et il n'est pas évident que ça le devienne — l'argument opposé est — les lecteurs posent généralement un verrou pour un temps très court alors devraient-ils réellement être privés lorsque l'écrivain pose un verrou pour une période potentiellement longue ?

Les verrous tournant « gros-lecteur » sont une forme de verrou tournant en lecture-écriture très optimisé pour des accès en lecture très légers, avec une pénalisation des écritures. Il y a un nombre limité de verrous gros-lecteur — actuellement il en existe seulement deux, dont un n'est utilisé que sur le sparc64 (global irq) et l'autre n'est utilisé que pour le réseau. Dans tous les autres cas où les modèles d'accès ne collent pas à l'un de ces deux scénarios, on doit utiliser des verrous tournant basiques. Vous ne pouvez pas bloquer pendant que n'importe quelle sorte de verrou tournant est maintenu.

Les verrous tournants sont fournis en trois saveurs : simple (plain), _irq() et _bh().

La raison pour laquelle vous ne pouvez pas utiliser de spin_lock() simples si vous êtes en concurrence avec des gestionnaires d'interruption, c'est que si vous en posez un et qu'une interruption survienne sur le même processeur, il attendra indéfiniment la levée du verrou : le propriétaire du verrou ayant été interrompu, ne continuera pas tant que le gestionnaire d'interruption n'aura pas retourné.

L'utilisation la plus courante des verrous tournant est pour accéder à  des structures de données partagées entre les contextes des processus utilisateur et des gestionnaires d'interruption :

spinlock_t my_lock = SPIN_LOCK_UNLOCKED;

my_ioctl()
{
	spin_lock_irq(&my_lock);
	/* section critique */
	spin_unlock_irq(&my_lock);
}

my_irq_handler()
{
	spin_lock(&lock);
	/* section critique */
	spin_unlock(&lock);
}

Il y a deux choses à  remarquer dans cet exemple :

Parfois, pendant l'accès à  une structure de données partagées, il faut effectuer des opérations qui peuvent bloquer, par exemple la copie de données dans l'espace utilisateur. La primitive de verrouillage disponible pour de tels scénarios sous Linux est appelée sémaphore. Il y a deux types de sémaphores : basique et lecture/écriture. En fonction de la valeur initiale du sémaphore, on peut obtenir soit une exclusion mutuelle (valeur initiale de 1) soit un type d'accès plus sophistiqué.

Les sémaphores en lecture-écriture diffèrent des sémaphores basiques de la même façon que les verrous tournant en lecture-écriture diffèrent des verrous tournant basiques : on peut avoir plusieurs lecteurs au même instant mais seulement un écrivain et il ne peut y avoir de lecteurs pendant qu'il y a des écrivains — i.e. l'écrivain bloque tous les lecteurs et les nouveaux lecteurs sont bloqués tant qu'un écrivain attend.

De plus, les sémaphores basiques peuvent être interrompus — juste en utilisant les opérations down/up_interruptible() au lieu des simples down()/up() et en vérifiant la valeur retourné par down_interruptible() : ce ne sera pas zéro si l'opération est interrompue.

Utiliser les sémaphores pour l'exclusion mutuelle est la solution idéale dans le cas où une section de code critique peut appeler par référence des fonction inconnues enregistrées par d'autres sous-systèmes/modules, i.e. l'appelant ne peut pas savoir à  priori si la fonction bloque ou non.

Un exemple simple de l'utilisation d'un sémaphore dans kernel/sys.c, est l'implémentation des appels systèmes gethostname(2)/sethostname(2).

asmlinkage long sys_sethostname(char *name, int len)
{
        int errno;

        if (!capable(CAP_SYS_ADMIN))
                return -EPERM;
        if (len < 0 || len > __NEW_UTS_LEN)
                return -EINVAL;
        down_write(&uts_sem);
        errno = -EFAULT;
        if (!copy_from_user(system_utsname.nodename, name, len)) {
                system_utsname.nodename[len] = 0;
                errno = 0;
        }
        up_write(&uts_sem);
        return errno;
}

asmlinkage long sys_gethostname(char *name, int len)
{
        int i, errno;

        if (len < 0)
                return -EINVAL;
        down_read(&uts_sem);
        i = 1 + strlen(system_utsname.nodename);
        if (i > len)
                i = len;
        errno = 0;
        if (copy_to_user(name, system_utsname.nodename, i))
                errno = -EFAULT;
        up_read(&uts_sem);
        return errno;
}

Les points à  remarquer dans cet exemple sont :

Bien que l'implémentation des sémaphores et des sémaphores lecture-écriture de Linux soit très sophistiquée, on peut imaginer des scénarios qui ne sont pas encore implémentés, par exemple il n'y a pas de concept de sémaphores lecture-écriture interruptibles. C'est évidemment parce qu'il n'y a pas de situation du monde réel qui nécessite ces implémentations de primitives exotiques.

Linux est un système d'exploitation monolithique et malgré toute la publicité moderne à  propos des « avantages » offerts par les systèmes d'exploitation basés sur des micro-noyaux, la vérité reste (dixit Linus Torvalds lui même) :

… considérer la transmission de messages comme l'opération de 
base d'un système d'exploitation n'est qu'un exercice d'informatique 
masturbatoire. Peut-être que cela vous procure du plaisir, mais vous 
n'obtenez rien de FAIT dans la réalité.

(… message passing as the fundamental operation of the OS is just 
an exercise in computer science masturbation. It may feel good, but you
don't actually get anything DONE.)

Par conséquent, Linux est et restera toujours basé sur une conception monolithique, ce qui signifie que tous les sous-systèmes s'exécutent dans le même mode privilégié et partagent le même espace d'adressage ; la communication entre eux s'accomplit par le biais d'appels aux fonctions C habituelles.

Cependant, bien que répartir les fonctionnalités du noyau dans des « processus » séparés comme cela se fait dans les micro-noyaux soit absolument une mauvaise idée, découper en modules noyau chargeables dynamiquement à la demande peut être souhaitable dans certaines circonstances (i.e. sur les machines avec peu de mémoire ou pour les noyaux d'installation qui autrement contiendraient des pilotes de périphériques ISA auto-testés qui sont mutuellement exclusifs). La décision d'inclure le support pour les modules chargeables est prise à  la compilation et est déterminée par l'option CONFIG_MODULES. Le support pour le chargement automatique des modules via le mécanisme request_module() est une option de compilation séparée (CONFIG_KMOD).

Les fonctionnalités suivantes peuvent être implémentées en modules chargeables sous Linux :

Il n'y a que peu de choses qui ne peuvent pas être implémentées comme des modules sous Linux (probablement parce que les rendre modulaires n'aurait aucun sens) :

Linux fournit plusieurs appels systèmes pour aider au chargement des modules :

L'interface de commande disponible pour les utilisateurs consiste en :

On peut charger manuellement un module en utilisant insmod ou modprobe, mais le module peut aussi être chargé automatiquement par le noyau quand une fonction particulière est requise. L'interface du noyau prévue pour cela est une fonction appelée request_module(name) qui est exportée vers les modules, ainsi les modules peuvent eux-mêmes charger d'autres modules. request_module(name) crée en interne un thread noyau qui « execs »-ute dans l'espace utilisateur la commande modprobe -s -k nom_du_module, en utilisant l'interface noyau standard exec_usermodehelper() (qui est aussi exportée vers les modules). La fonction renvoie 0 en cas de succès, mais il n'est généralement pas utile de tester le code de retour de request_module(). Il vaut mieux utiliser ce modèle :

if (check_some_feature() == NULL)
    request_module(module);
if (check_some_feature() == NULL)
    return -ENODEV;

Par exemple, fs/block_dev.c:get_blkfops() suit ce modèle pour charger le module block-major-N quand un essai est fait pour ouvrir le périphérique bloc de majeur N. évidemment, il n'y a pas de module appelé block-major-N (Les développeurs Linux choisissent des noms sensés pour leurs modules), ce nom est associé au bon module en utilisant le fichier /etc/modules.conf. Cependant, pour les plus connus des nombres majeur (et pour d'autre modules) les commandes modprobe/insmod savent quels modules réels charger sans avoir besoin d'un alias explicite dans /etc/modules.conf.

Un bon exemple de chargement d'un module est dans l'appel système mount(2). L'appel système mount(2) prend un type de système de fichier comme argument sous la forme d'une chaîne de caractères que fs/super.c:do_mount() passe ensuite à  fs/super.c:get_fs_type() :

static struct file_system_type *get_fs_type(const char *name)
{
        struct file_system_type *fs;

        read_lock(&file_systems_lock);
        fs = *(find_filesystem(name));
        if (fs && !try_inc_mod_count(fs->owner))
                fs = NULL;
        read_unlock(&file_systems_lock);
        if (!fs && (request_module(name) == 0)) {
                read_lock(&file_systems_lock);
                fs = *(find_filesystem(name));
                if (fs && !try_inc_mod_count(fs->owner))
                        fs = NULL;
                read_unlock(&file_systems_lock);
        }
        return fs;
}

Une ou deux choses à  remarquer dans cette fonction :

Quand un module est chargé dans le noyau, il peut référencer tous les symboles exportés comme publics par le noyau en utilisant la macro EXPORT_SYMBOL() ou par les autres modules actuellement chargés. Si le module utilise des symboles d'un autre module, il est marqué comme dépendant de ce module durant le recalcul des dépendances, effectué à  l'amorçage par la commande depmod -a (par exemple après l'installation d'un nouveau noyau).

Habituellement, l'ensemble des modules doivent correspondre à  la version des interfaces noyau qu'ils utilisent, ce qui sous Linux signifie simplement « la version du noyau » car il n'y a pas en général de mécanisme de gestion de version de l'interface noyau. Cependant il existe une fonctionnalité limitée appelée « module versioning » ou CONFIG_MODVERSIONS qui permet d'éviter de recompiler les modules quand on change de noyau. Ce qui ce passe ici c'est que la table des symboles noyau est traitée différemment pour les accès internes et pour l'accès depuis les modules. Les éléments de la partie publique (i.e. exportée) de la table des symboles sont construits en faisant des sommes de contrôle 32bit des déclarations C. Donc, pour résoudre un symbole utilisé par un module pendant le chargement, le chargeur doit faire correspondre la représentation complète du symbole y compris la somme de contrôle ; il refusera de charger le module si les symboles différent. Ce qui se produit seulement quand à  la fois le noyau et le module sont compilés avec le « module versioning » activé. Si l'un d'entre eux utilise le nom originel du symbole, le chargeur essaie simplement de faire correspondre la version déclarée par le module et celle exportée par le noyau et refuse de charger le module si elles différent.

Dans le but de supporter de multiples types de systèmes de fichiers, Linux contient un niveau d'interface noyau spécial appelé VFS (Virtual Filesystem Switch ou commutateur de systèmes de fichiers virtuels), similaire à l'interface vnode/vfs trouvé dans les dérivés de SVR4 (il provient à l'origine des implémentations BSD et Sun).

Le cache inode Linux est implémenté par un seul fichier, fs/inode.c, qui consiste en 977 lignes de code. Il est intéressant de noter qu'il n'y a pas eu tant de changements ces 5-7 dernières années : on peut encore reconnaître un peu de code en comparant la dernière version avec, disons, la 1.3.42.

Voici la structure du cache inode de Linux :

Les listes de types sont ancrées sur inode->i_list, la table de hachage sur inode->i_hash. Chaque inode peut être dans une table de hachage et dans une seule liste de type (utilisé, inutilisé, modifié).

Toutes ces listes sont protégées par un unique verrou tournant : inode_lock.

Le sous-système de cache inode est initialisé quand la fonction inode_init() est appelée depuis init/main.c:start_kernel(). La fonction est marquée __init, ce qui veut dire que son code est supprimé plus tard. On lui passe un seul argument — le nombre de pages physiques du système. C'est ainsi que le cache inode peut se configurer lui même en fonction de la quantité de mémoire disponible, i.e. créer une plus grande table de hachage s'il y a assez de mémoire.

Il n'y a qu'une seule information statistique à  propos du cache inode, le nombre d'inodes inutilisés, stocké dans inodes_stat.nr_unused et accessible aux programmes utilisateurs par les fichiers /proc/sys/fs/inode-nr et /proc/sys/fs/inode-state.

On peut examiner une de ces liste avec gdb s'exécutant sur un noyau en activité :

(gdb) printf "%d\n", (unsigned long)(&((struct inode *)0)->i_list)
8
(gdb) p inode_unused
$34 = 0xdfa992a8
(gdb) p (struct list_head)inode_unused
$35 = {next = 0xdfa992a8, prev = 0xdfcdd5a8}
(gdb) p ((struct list_head)inode_unused).prev
$36 = (struct list_head *) 0xdfcdd5a8
(gdb) p (((struct list_head)inode_unused).prev)->prev
$37 = (struct list_head *) 0xdfb5a2e8
(gdb) set $i = (struct inode *)0xdfb5a2e0
(gdb) p $i->i_ino
$38 = 0x3bec7
(gdb) p $i->i_count
$39 = {counter = 0x0}

Remarquez que la valeur 8 a été déduite de l'adresse 0xdfb5a2e8 pour obtenir l'adresse de struct inode (0xdfb5a2e0) d'après la définition de la macro list_entry() dans include/linux/list.h.

Pour comprendre comment le cache inode fonctionne, nous allons suivre la vie de l'inode d'un fichier régulier sur un système de fichier ext2 quand il est ouvert et fermé :

fd = open("file", O_RDONLY);
close(fd);

L'appel système open(2) est implémenté dans la fonction fs/open.c:sys_open et le travail effectif est réalisé par la fonction fs/open.c:filp_open(), qui est divisée en deux parties :

La fonction open_namei() interagit avec le cache dentry via path_walk(), qui à  son tour appelle real_lookup(), qui invoque la méthode inode_operations->lookup() spécifique au système de fichiers. Le rôle de cette méthode est de trouver l'entrée dans le répertoire parent qui correspond au nom et ensuite faire iget(sb, ino) pour avoir l'inode correspondant — ce qui nous amène dans le cache inode. Quand l'inode est lu, dentry est instancié grâce à  d_add(dentry, inode). Pendant que nous y sommes, remarquez que pour les systèmes de fichiers de style UNIX qui ont adopté le concept du numéro d'inode sur disque, il revient à  la méthode de recherche de gérer l'ordre des octets (endianness) spécifique au format du CPU, i.e. si le numéro de l'inode d'entrée du répertoire en binaire (fs-specific) est au format 32 bits petit boutien (little-endian) on peut faire :

unsigned long ino = le32_to_cpu(de->inode);
inode = iget(sb, ino);
d_add(dentry, inode);

Ainsi, quand on ouvre un fichier, on utilise iget(sb, ino) qui en réalité est iget4(sb, ino, NULL, NULL), et on :

Maintenant, regardons ce qui ce passe quand on ferme le descripteur de ce fichier. L'appel système close(2) est implémenté dans la fonction fs/open.c:sys_close(), qui appelle do_close(fd, 1) qui annule (remplace par NULL) le descripteur du fichier dans la table des descripteur des fichiers processus et invoque la fonction filp_close() qui effectue la plus grande partie du travail. Les choses intéressantes se passent dans fput(), qui vérifie si ce descripteur était la dernière référence au fichier, et si c'est le cas appelle fs/file_table.c:_fput() qui appelle __fput(), là  ou les interactions avec dcache ont lieu (donc avec le cache inode aussi — rappelez vous que dcache est le maître du cache inode!). fs/dcache.c:dput() fait un dentry_iput() qui nous ramène au cache inode via iput(inode), alors essayons de comprendre fs/inode.c:iput(inode) :

Le travail effectué par iput() sur la dernière référence de l'inode est relativement complexe, alors on lui consacrera une liste propre :

Le noyau Linux fournit un mécanisme permettant de créer de nouveaux systèmes de fichiers avec un minimum d'effort, ceci pour des raisons historiques :

Considérons les étapes nécessaire à  l'implémentation d'un système de fichiers sous Linux.

Le code nécessaire peut soit être un module chargeable dynamiquement, soit être statiquement lié au noyau, ce qui est fait de façon très transparente sous Linux. Il suffit de créer et initialiser une structure struct file_system_type et de l'enregistrer auprès du VFS en utilisant la fonction register_filesystem() comme dans l'exemple de fs/bfs/inode.c :

#include <linux/module.h>
#include <linux/init.h>


static struct super_block *bfs_read_super(struct super_block *, void *, int);

static DECLARE_FSTYPE_DEV(bfs_fs_type, "bfs", bfs_read_super);

static int __init init_bfs_fs(void)
{
        return register_filesystem(&bfs_fs_type);
}

static void __exit exit_bfs_fs(void)
{
        unregister_filesystem(&bfs_fs_type);
}

module_init(init_bfs_fs)
module_exit(exit_bfs_fs)

Les macros module_init()/module_exit() assurent que, lorsque BFS est compilé comme un module, les fonctions init_bfs_fs() et exit_bfs_fs() deviennent respectivement init_module() et cleanup_module() ; si BFS est lié statiquement dans le noyau, le code exit_bfs_fs() disparaît puisqu'il est inutile.

struct file_system_type est déclaré dans include/linux/fs.h :

struct file_system_type {
        const char *name;
        int fs_flags;
        struct super_block *(*read_super) (struct super_block *, void *, int);
        struct module *owner;
        struct vfsmount *kern_mnt; /* Pour monter le noyau, si c'est un FS_SINGLE fs */
        struct file_system_type * next;
};

Les champs eux-mêmes sont décrits ci-dessous :

Le travail de la fonction read_super() est de remplir les champs du super-bloc, allouer l'inode racine (root) et initialiser toutes les informations privées du système de fichiers associées à  cette instance montée de système de fichiers. Donc, typiquement le read_super() :

Sous Linux il y a plusieurs niveaux d'indirection entre le descripteur de fichier utilisateur et la structure inode du noyau. Quand un processus fait un appel système open(2), le noyau retourne un petit entier non négatif qui peut être utilisé pour les opérations d'entrée/sortie suivantes sur ce fichier. Cet entier est un index dans un tableau de pointeurs sur struct file. Chaque structure de fichier pointe sur un dentry via file->f_dentry. Et chaque dentry pointe sur un inode via dentry->d_inode.

Chaque tâche contient un champ tsk->files qui est un pointeur sur struct files_struct défini dans include/linux/sched.h :

/*
 * Ouvrir la structure du tableau des fichiers
 */
struct files_struct {
        atomic_t count;
        rwlock_t file_lock;
        int max_fds;
        int max_fdset;
        int next_fd;
        struct file ** fd;      /* tableau fd courant */
        fd_set *close_on_exec;
        fd_set *open_fds;
        fd_set close_on_exec_init;
        fd_set open_fds_init;
        struct file * fd_array[NR_OPEN_DEFAULT];
};

file->count est un compteur de références, incrémenté par get_file() (appelé habituellement par fget()) et décrémenté par fput() et par put_filp(). La différence entre fput() et put_filp(), c'est que fput() fait un travail supplémentaire, nécessaire habituellement pour les fichiers réguliers, comme libérer les verrous flocks ou le dentry, etc, tandis que put_filp() ne fait que manipuler les structures de la table de fichier, i.e. décrémente le compteur, retire le fichier de anon_list et l'ajoute à  free_list, sous le contrôle du verrou tournant files_lock.

tsk->files peut être partagé entre parent et enfant si le thread enfant a été créé en utilisant l'appel système clone() avec CLONE_FILES mis dans l'argument drapeaux. On peut voir cela dans kernel/fork.c:copy_files() (appelé par do_fork()) qui ne fait qu'incrémenter file->count si CLONE_FILES est mis au lieu de copier la table des descripteurs de fichiers selon l'habitude consacrée par la tradition du classique fork(2) UNIX.

Quand un fichier est ouvert, la structure de fichier allouée pour lui est installée à  la position current->files->fd[fd] et un bit fd est mis dans le bitmap current->files->open_fds. Tout ceci est réalisé sous le contrôle du verrou tournant en lecture-écriture current->files->file_lock. Quand le descripteur est fermé, le bit fd est nettoyé dans current->files->open_fds et current->files->next_fd est rendu égal à  fd, indication qui aidera à  trouver le premier descripteur libre la prochaine fois que ce processus voudra ouvrir un fichier.

La structure de fichier est déclarée dans include/linux/fs.h :

struct fown_struct {
        int pid;                /* le pid ou -pgrp auquel SIGIO doit être envoyé */
        uid_t uid, euid;        /* uid/euid du processus définissant le propriétaire */
        int signum;             /* le signal posix.1b rt à  envoyer sur l'IO */
};

struct file {
        struct list_head        f_list;
        struct dentry           *f_dentry;
        struct vfsmount         *f_vfsmnt;
        struct file_operations  *f_op;
        atomic_t                f_count;
        unsigned int            f_flags;
        mode_t                  f_mode;
        loff_t                  f_pos;
        unsigned long           f_reada, f_ramax, f_raend, f_ralen, f_rawin;
        struct fown_struct      f_owner;
        unsigned int            f_uid, f_gid;
        int                     f_error;

        unsigned long           f_version;
  
        /* nécessaire pour les pilotes de tty, et peut-être pour d'autres */
        void                    *private_data; 
};

Regardons les divers champs de struct file :

Maintenant regardons la structure file_operations qui contient les méthodes pouvant être invoquées sur les fichiers. Rappelons nous que c'est une copie de inode->i_fop évalué par la méthode s_op->read_inode(). Elle est déclarée dans include/linux/fs.h :

struct file_operations {
  struct module *owner;
  loff_t (*llseek) (struct file *, loff_t, int);
  ssize_t (*read) (struct file *, char *, size_t, loff_t *);
  ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
  int (*readdir) (struct file *, void *, filldir_t);
  unsigned int (*poll) (struct file *, struct poll_table_struct *);
  int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
  int (*mmap) (struct file *, struct vm_area_struct *);
  int (*open) (struct inode *, struct file *);
  int (*flush) (struct file *);
  int (*release) (struct inode *, struct file *);
  int (*fsync) (struct file *, struct dentry *, int datasync);
  int (*fasync) (int, struct file *, int);
  int (*lock) (struct file *, int, struct file_lock *);
  ssize_t (*readv) (struct file *, const struct iovec *,
                    unsigned long, loff_t *);
  ssize_t (*writev) (struct file *, const struct iovec *,
                     unsigned long, loff_t *);
};

Sous Linux, les informations à  propos des systèmes de fichiers montés sont gardées dans deux structures séparées — super_block et vfsmount. La raison en est que Linux autorise le montage du même système de fichiers (périphérique bloc) sur plusieurs points de montage, ce qui signifie que le même super_block peut correspondre à  des structures vfsmount multiples.

Regardons d'abord struct super_block, déclarée dans include/linux/fs.h :

struct super_block {
    struct list_head        s_list;      /* À laisser au début */
    kdev_t                  s_dev;
    unsigned long           s_blocksize;
    unsigned char           s_blocksize_bits;
    unsigned char           s_lock;
    unsigned char           s_dirt;
    struct file_system_type *s_type;
    struct super_operations *s_op;
    struct dquot_operations *dq_op;
    unsigned long           s_flags;
    unsigned long           s_magic;
    struct dentry           *s_root;
    wait_queue_head_t       s_wait;
    struct list_head        s_dirty;     /* inodes modifiés */
    struct list_head        s_files;

    struct block_device     *s_bdev;
    struct list_head        s_mounts;    /* vfsmount(s) de celui-ci */
    struct quota_mount_options s_dquot;  /* options spécifiques aux quotas */

    union {
            struct minix_sb_info    minix_sb;
            struct ext2_sb_info     ext2_sb;
            ... all filesystems that need sb-private info ...
            void                    *generic_sbp;
    } u;
   /*
    * Le champ suivant n'est *que* pour VFS. Aucun système de fichiers 
    * n'a affaire à  lui, même pour jeter un œil. Vous aurez été 
    * prévenus.
    */
    struct semaphore s_vfs_rename_sem;    /* Usine à  gaz */

   /* Le champ suivant est utilisé par knfsd pour convertir un handle de  
    * fichier (basé sur le numéro d'inode) en un dentry. Lorsqu'il dessine  
    * un chemin dans l'arbre du dcache à  partir du bas, il peut y avoir 
    * provisoirement un sous-chemin de dentrys qui n'est pas connecté à  
    * l'arbre principal. Ce sémaphore assure qu'il n'y ait jamais qu'un seul
    * chemin libéré ainsi par système de fichiers. Noter qu'avoir des 
    * fichiers (ou n'importe quoi d'autre, en dehors d'un répertoire) 
    * non connectés est autorisé, mais pas d'avoir des répertoires non 
    * connectés…
    */
    struct semaphore s_nfsd_free_path_sem;
};

Les différents champs de la structure super_block sont :

Les opérations du super-bloc sont décrites dans la structure super_operations déclarée dans include/linux/fs.h :

struct super_operations {
        void (*read_inode) (struct inode *);
        void (*write_inode) (struct inode *, int);

        void (*put_inode) (struct inode *);
        void (*delete_inode) (struct inode *);
        void (*put_super) (struct super_block *);
        void (*write_super) (struct super_block *);
        int (*statfs) (struct super_block *, struct statfs *);
        int (*remount_fs) (struct super_block *, int *, char *);
        void (*clear_inode) (struct inode *);
        void (*umount_begin) (struct super_block *);
};

Alors regardons ce qu'il se passe quand nous montons un système de fichiers présent sur un disque (FS_REQUIRES_DEV). L'implémentation de l'appel système mount(2) est dans fs/super.c:sys_mount() qui n'est qu'un emballage qui copie les options, le type de système de fichiers et le nom du périphérique pour la fonction do_mount() qui fait réellement le travail :

Comme exemple simple de système de fichiers qui ne requiert pas un périphérique bloc pour être monté, considérons pipefs dans fs/pipe.c. Le préambule de ce fichier va droit au but et ne nécessite guère d'explications :

static DECLARE_FSTYPE(pipe_fs_type, "pipefs", pipefs_read_super,
        FS_NOMOUNT|FS_SINGLE);

static int __init init_pipe_fs(void)
{
        int err = register_filesystem(&pipe_fs_type);
        if (!err) {
                pipe_mnt = kern_mount(&pipe_fs_type);
                err = PTR_ERR(pipe_mnt);
                if (!IS_ERR(pipe_mnt))
                        err = 0;
        }
        return err;
}

static void __exit exit_pipe_fs(void)
{
        unregister_filesystem(&pipe_fs_type);
        kern_umount(pipe_mnt);
}

module_init(init_pipe_fs)
module_exit(exit_pipe_fs)

Le système de fichiers est du type FS_NOMOUNT|FS_SINGLE, ce qui signifie qu'il ne peut pas être monté depuis l'espace utilisateur et qu'il ne peut avoir qu'un super-bloc dans tout le système. Dire que le fichier est de type FS_SINGLE signifie aussi qu'il doit être monté via kern_mount() une fois qu'il a réussi à  s'enregistrer via register_filesystem(), et c'est exactement ce qui se passe dans init_pipe_fs(). Le seul bug de cette fonction est que si kern_mount() échoue (i.e. parce que kmalloc() échoue dans l'allocation add_vfsmnt()), alors le système de fichiers reste enregistré tandis que l'initialisation du module a échoué. Ce qui fera « planter » cat /proc/filesystems. (je viens juste d'envoyer un patch à  Linus mentionnant cela, bien que ce ne soit pas un vrai bug aujourd'hui car pipefs ne peut pas être compilé comme un module, la fonction devrait être réécrite en gardant à  l'esprit que dans le futur il pourrait devenir un module).

Le résultat de register_filesystem() est que pipe_fs_type est lié à  la liste file_systems si bien qu'on peut lire /proc/filesystems et y trouver l'entrée « pipefs » avec un drapeau « nodev » indiquant que FS_REQUIRES_DEV n'est pas mis. Il faudrait vraiment améliorer le fichier /proc/filesystems pour qu'il supporte tous les nouveaux drapeaux FS_ (et j'ai écrit un patch pour le faire) mais on ne peut pas le faire parce que cela planterait toutes les applications utilisateur qui l'utilisent. Bien que les interfaces du noyau Linux changent toutes les cinq minutes (toujours en mieux), quand on en vient à  la compatibilité dans l'espace utilisateur, Linux est un système d'exploitation très conservateur qui permet à  beaucoup d'applications d'être utilisées longtemps sans recompilation.

Le résultat de kern_mount() est que :

Maintenant que le système de fichiers est enregistré et monté dans le noyau, nous pouvons l'utiliser. Le point d'entrée du système de fichiers pipefs est l'appel système pipe(2), implémenté dans la fonction sys_pipe() dépendante de l'architecture mais le travail effectif est fait par une fonction portable fs/pipe.c:do_pipe(). Regardons do_pipe(). Les interactions avec pipefs se produisent quand do_pipe() appelle get_pipe_inode() pour allouer un nouvel inode pipefs. Pour cet inode, inode->i_sb prend la valeur du super-bloc de pipefs pipe_mnt->mnt_sb, les opérations fichier i_fop sont mises à  rdwr_pipe_fops et le nombre de lecteurs et d'écrivains (contenu dans inode->i_pipe) est fixé à  1. La raison pour maintenir un champ inode i_pipe séparé au lieu de le laisser dans l'union fs-private est que les tubes (pipes) et les FIFO partagent le même code et les FIFO peuvent exister sur d'autre systèmes de fichier qui utilisent d'autres chemins d'accès dans la même union, ce qui est du très mauvais C et ne fonctionne que par pur hasard. Alors, oui, les noyaux 2.2.x fonctionnent par chance et s'arrêteront dès que vous réarrangerez tant soit peu les champs dans l'inode.

Chaque appel système pipe(2) incrémente un compteur de références de l'instance pipe_mnt.

Sous Linux, les pipes ne sont pas symétrique (pipes bidirectionnels ou STREAM), i.e. les deux côtés du fichier ont des opérations file->f_op différentes — read_pipe_fops et write_pipe_fops respectivement. Écrire sur le côté lecture retourne EBADF de même que lire sur le côté écriture.

Comme exemple simple d'un système de fichiers Linux sur disque, considérons BFS. Le préambule du module BFS est dans fs/bfs/inode.c :

static DECLARE_FSTYPE_DEV(bfs_fs_type, "bfs", bfs_read_super);

static int __init init_bfs_fs(void)
{
        return register_filesystem(&bfs_fs_type);
}

static void __exit exit_bfs_fs(void)
{
        unregister_filesystem(&bfs_fs_type);
}

module_init(init_bfs_fs)
module_exit(exit_bfs_fs)

Une macro spéciale pour déclarer le fstype DECLARE_FSTYPE_DEV() est utilisée pour mettre le fs_type->flags à  FS_REQUIRES_DEV ce qui signifie que BFS requiert un vrai périphérique bloc pour être monté.

La fonction d'initialisation du module enregistre le système de fichiers auprès du VFS et la fonction de nettoyage (présente seulement quand BFS est configuré en tant que module) le dés-enregistre.

Une fois le système de fichiers enregistré, on peut procéder au montage, ce qui invoquera la méthode fs_type->read_super() implémentée dans fs/bfs/inode.c:bfs_read_super(). Elle fait ce qui suit :

Quand la fonction read_super() est retournée avec succès, le VFS obtient une référence sur le module du système de fichiers via l'appel à  get_filesystem(fs_type) dans fs/super.c:get_sb_bdev() et une référence au périphérique bloc.

Maintenant, examinons ce qu'il se passe quand on fait une entrée/sortie sur le système de fichiers. Nous avons déjà  examiné comment les inodes sont lus quand iget() est appelé et comment ils sont relâchés sur un iput(). La lecture des inodes configure, parmi d'autres choses, inode->i_op et inode->i_fop ; l'ouverture d'un fichier propage inode->i_fop vers file->f_op.

Parcourons le code de l'appel système link(2). L'implémentation de l'appel système est dans fs/namei.c:sys_link() :

D'autres opérations sur les inodes comme unlink()/rename(), etc, fonctionnent de la même façon, cela ne vaut pas la peine de les expliquer toutes en détails.

Linux supporte le chargement des binaires des applications utilisateur depuis les disques. Plus intéressant, les binaires peuvent être stockés sous différents formats et la réponse du système d'exploitation aux programmes via les appels systèmes peut dévier de la norme (la norme étant le comportement de Linux) si nécessaire, afin d'émuler le comportement d'appels systèmes d'autre versions (Solaris, UnixWare, etc). C'est à  cela que servent les domaines d'exécution et les formats binaires.

Chaque tâche Linux a une personnalité stockée dans sa task_struct (p->personality). Les personnalités existantes à  l'heure actuelle (soit dans le noyau officiel ou par l'ajout d'un patch) incluent le support pour FreeBSD, Solaris, UnixWare, OpenServer et beaucoup d'autres systèmes d'exploitation populaires. La valeur de current->personality se décompose en deux partie :

En changeant la personnalité, on peut changer la façon dont le système d'exploitation traite certains appels système, par exemple l'ajout de STICKY_TIMEOUT à current->personality fait que l'appel système select(2) préserve la valeur du dernier argument (timeout) au lieu de stocker le temps d'activité. Quelques programmes bogués comptent sur des systèmes d'exploitation bogués (pas Linux) et donc Linux fournit un moyen d'émuler les bugs dans les cas où le code source n'est pas disponible et donc que les bugs ne peuvent pas être corrigés.

Le domaine d'exécution est un ensemble de personnalités contiguës implémentées par un seul module. Habituellement, il y a un seul domaine d'exécution qui implémente une seule personnalité, mais quelquefois il est possible d'implémenter des personnalités « proches » dans un seul module sans trop de conditions à  remplir.

Les domaines d'exécution sont implémentés dans kernel/exec_domain.c et ont été complètement récrits pour les noyaux 2.4, par rapport aux 2.2.x. La liste des domaines d'exécution couramment supportés par le noyau, avec l'ensemble des personnalités qu'ils supportent, est disponible dans le fichier /proc/execdomains. Les domaines d'exécution, à  l'exception de PER_LINUX, peuvent être implémentés comme des modules chargeables dynamiquement.

L'interface utilisateur consiste en l'appel système personality(2), qui fixe la personnalité actuelle du processus ou renvoie la valeur de current->personality quand l'argument personnalité a la valeur impossible 0xffffffff. Évidemment, le comportement de cet appel système lui-même ne dépend pas de la personnalité.

L'interface noyau pour l'enregistrement des domaines d'exécution est constitué de deux fonctions :

La raison pour laquelle exec_domains_lock est en lecture-écriture est que seules les requêtes d'enregistrement et de dés-enregistrement modifient la liste, tandis que faire cat /proc/filesystems appelle fs/exec_domain.c:get_exec_domain_list(), qui n'a besoin que d'un accès en lecture à  la liste. L'enregistrement d'un nouveau domaine d'exécution définit un « lcall7 handler » et une table de conversion des numéros de signaux. Actuellement, le patch ABI étend ce concept de domaine d'exécution pour inclure des informations supplémentaires (comme les options de socket, les types de socket, les familles d'adresses, les tables d'errno (symboles d'erreurs)).

Les formats binaires sont implémentés de manière similaire, i.e. une liste chaînée simple de formats est définie dans fs/exec.c et est protégée par un verrou binfmt_lock en lecture-écriture. Comme pour exec_domains_lock, le binfmt_lock en lecture est posé dans la plupart des cas sauf pour les enregistrements/dés-enregistrements de format binaire. L'enregistrement d'un nouveau format étend l'appel système execve(2) par de nouvelles fonctions load_binary()/load_shlib() ainsi que core_dump(). La méthode load_shlib() n'est utilisée que par le vieil appel système uselib(2) pendant que la méthode load_binary() est appelée par search_binary_handler() depuis do_execve() qui implémente l'appel système execve(2).

La personnalité du processus est déterminée au chargement du format binaire par la méthode load_binary() correspondante en utilisant quelques heuristiques. Par exemple, pour reconnaître les binaires UnixWare7, on marque d'abord le binaire en utilisant l'utilitaire elfmark(1), qui fixe e_flags de l'entête ELF à  la valeur magique 0x314B4455 qui a été détectée au moment du chargement ELF et la personnalité courante current->personality est mise à  PER_UW7. Si cette heuristique échoue, alors on en utilise une plus générique, telle que considérer que si l'emplacement de l'interpréteur ELF est /usr/lib/ld.so.1 ou /usr/lib/libc.so.1, ceci indique que le binaire est un SVR4 et mettre alors la personnalité à  PER_SVR4. On peut écrire un petit programme utilitaire qui utilise les capacité du ptrace(2) de Linux pour exécuter le code pas à  pas et ainsi forcer un programme à  s'exécuter dans n'importe quelle personnalité.

Une fois que la personnalité est connue (et par conséquent current->exec_domain), les appels système sont pris en charge comme suit. Admettons que le processus fasse un appel système par le biais de l'instruction de porte lcall7. Cela transfert le contrôle à  ENTRY(lcall7) de arch/i386/kernel/entry.S comme cela a été préparé dans arch/i386/kernel/traps.c:trap_init(). Après avoir converti la disposition de la pile de façon appropriée, entry.S:lcall7 obtient un pointeur sur exec_domain depuis current puis le décalage (offset) du gestionnaire lcall7 dans exec_domain (qui est fixé en dur à  4 dans le code assembleur, si bien que vous ne pouvez pas décaler le champs handler dans la déclaration C de la structure struct exec_domain) et va là bas. Donc, en C, ça ressemble à  ceci :

static void UW7_lcall7(int segment, struct pt_regs * regs)
{
       abi_dispatch(regs, &uw7_funcs[regs->eax & 0xff], 1);
}

où abi_dispatch() est une enveloppe autour de la table des pointeurs de fonction qui implémente les appels système uw7_funcs de la personnalité actuelle.

Les fonctions décrites dans cette partie implémentent les mécanismes de sémaphore au niveau utilisateur. Remarquez que cette implémentation repose sur l'utilisation des sémaphores et des verrous tournants du noyau. Pour éviter toute confusion, le terme « sémaphore noyau » sera utilisé en référence aux sémaphores du noyau. Toutes les autres utilisations du mot « sémaphore » feront référence aux sémaphores du niveau utilisateur.

/* Une structure de données sem_array pour chaque ensemble de sémaphores 
   du système. */ 
struct sem_array {
    struct kern_ipc_perm sem_perm; /* permissions — voir ipc.h */
    time_t sem_otime; /* instant du dernier semop */
    time_t sem_ctime; /* instant du dernier changement */
    struct sem *sem_base; /* pointe sur le premier sémaphore du tableau */
    struct sem_queue *sem_pending; /* opérations suspendues à  exécuter */
    struct sem_queue **sem_pending_last; /* dernière operation suspendue */
    struct sem_undo *undo; /* les undos demandés pour ce tableau * /
    unsigned long sem_nsems; /* aucun sémaphore dans le tableau */
};

/* Une structure de sémaphore pour chaque sémaphore du système. */
struct sem {
    int     semval;     /* valeur courante */
    int     sempid;     /* pid de la dernière opération */
};

struct  seminfo {
    int semmap;
    int semmni;
    int semmns;
    int semmnu;
    int semmsl;
    int semopm;
    int semume;
    int semusz;
    int semvmx;
    int semaem;
};

struct semid64_ds {
    struct ipc64_perm sem_perm;  /* permissions — voir ipc.h */
    __kernel_time_t sem_otime;   /* instant du dernier semop */
    unsigned long   __unused1;
    __kernel_time_t sem_ctime;   /* instant de la dernière modification */
    unsigned long   __unused2;
    unsigned long   sem_nsems;   /* aucun sémaphore dans le tableau */
    unsigned long   __unused3;
    unsigned long   __unused4;
};

/* Une . */
struct sem_queue {
  struct sem_queue *  next;    /* entrée suivante dans la file */
  struct sem_queue ** prev;    /* entrée précédente dans la file, */
                               /* *(q->prev) == q */
  struct task_struct* sleeper; /* ce processus */
  struct sem_undo *   undo;    /* structure d'undo  */
  int                 pid;     /* identificateur du processus demandeur */
  int                 status;  /* statut d'exécution de l'opération */
  struct sem_array *  sma;     /* tableau de sémaphores pour les operations */
  int                 id;      /* identificateur interne du sémaphore */
  struct sembuf *     sops;    /* tableau des opérations suspendues */
  int                 nsops;   /* nombre d'opérations */
  int                 alter;   /* l'opération va modifier le sémaphore */
};

/* les appels systèmes semop prennent un tableau de ceux-ci. */
struct sembuf {
    unsigned short  sem_num;        /* index du sémaphore dans le tableau */
    short           sem_op;         /* operation sur le sémaphore */
    short           sem_flg;        /* options */
};

/* Chaque tâche a sa liste d'opérations à  annuler. Les annulations sont 
 * faites automatiquement quand le processus se termine.
 */
struct sem_undo {
  struct sem_undo *  proc_next;  /* entrée suivante pour ce processus */
  struct sem_undo *  id_next;    /* entrée suivante pour cet ensemble */
                                 /* de sémaphores */
  int                semid;      /* identificateur de l'ensemble de sémaphores */
  short *            semadj;     /* tableau d'adaptations, une par sémaphore */
};