Structure interne du noyau Linux 2.4

Date de mise à jour : 13 mai 2003

Par Tigran Aivazian (mail)
 Yaël Gomez (Adaptation française) (mail)
 Claire Boussard (Relecture de la version française) (mail)
 

Adaptation française du Linux Kernel 2.4 Internals

Une introduction au noyau Linux 2.4. Ce document a été réalisé comme support de cours donnés en interne par l'auteur chez VERITAS Software Ltd. Celui-ci travaille en tant qu'ingénieur senior Noyau Linux au sein de cette société.

I. Introduction

I-A. Dernière version de ce document

I-B. Droits d'utilisation

I-C. Remerciements

• Juan J. Quintela quintela CHEZ fi POINT udc POINT es,
• Francis Galiegue fg CHEZ mandrakesoft POINT com,
• Hakjun Mun juniorm CHEZ orgio POINT net,
• Matt Kraai kraai CHEZ alumni POINT carnegiemellon POINT edu,
• Nicholas Dronen ndronen CHEZ frii POINT com,
• Samuel S. Chessman chessman CHEZ tux POINT org,
• Nadeem Hasan nhasan CHEZ nadmm POINT com,
• Michael Svetlik m.svetlik CHEZ ssi TIRET schaefer TIRET peem POINT com pour les diverses corrections et suggestions.
• Le chapitre Linux Page Cache a été écrit par : Christoph Hellwig hch CHEZ caldera POINT de.
• Le chapitre Mécanismes IPC a été écrit par : Russell Weight weightr CHEZ us POINT ibm POINT com et Mingming Cao mcao CHEZ us POINT ibm POINT com.

I-D. Adaptation française

II. Amorçage (Booting)

II-A. Construire l'image du noyau Linux

1. Les fichiers sources C et assembleur sont compilés au format objet relogeable (.o) ELF et certains d'entre eux sont regroupés logiquement dans des archives (.a) en utilisant ar(1).
2. En utilisant ld(1), les .o et .a ci-dessus sont liés pour donner vmlinux qui est un fichier exécutable ELF 32-bit LSB 80386 non strippé (les symboles n'ont pas été nettoyés), statiquement lié.
3. System.map est produit par nm vmlinux, les symboles inutiles sont retirés.
4. On entre dans le répertoire arch/i386/boot.
5. Le code assembleur du secteur d'amorçage bootsect.S est pré-traité avec ou sans -D__BIG_KERNEL__ pour produire respectivement, selon que la cible est bzImage ou zImage, bbootsect.s ou bootsect.s.
6. bbootsect.s est assemblé et converti en un fichier « binaire brut » (raw binary) appelé bbootsect (ou bootsect.s assemblé et converti en binaire brut donnant bootsect pour zImage).
7. Le code Setup setup.S (setup.S inclut video.S) est pré-traité pour donner bsetup.s pour bzImage ou setup.s pour zImage. De la même façon que pour le code de bootsector, la différence réside en -D__BIG_KERNEL__, présent pour bzImage. Le résultat est converti en un « binaire brut » appelé bsetup.
8. On entre dans le répertoire arch/i386/boot/compressed et convertit /usr/src/linux/vmlinux en $tmppiggy (nom de fichier temporaire) au format binaire brut, en retirant les sections ELF .note et .comment.
9. gzip -9 < $tmppiggy > $tmppiggy.gz
10. On lie $tmppiggy.gz au format ELF relogeable (ld -r) piggy.o.
11. On compile les fonctions de compression head.S et misc.c (toujours dans le répertoire arch/i386/boot/compressed) en objets ELF head.o et misc.o.
12. On lie ensemble head.o, misc.o et piggy.o pour obtenir bvmlinux (ou vmlinux pour zImage, attention à ne pas le confondre avec /usr/src/linux/vmlinux!). Notez la différence entre -Ttext 0x1000 utilisé pour vmlinux et -Ttext 0x100000 pour bvmlinux, i.e. pour bzImage compressé le chargeur (loader) est chargé en haut.
13. On convertit bvmlinux en un « binaire brut » bvmlinux.out en enlevant les sections ELF .note et .comment.
14. On revient dans le répertoire arch/i386/boot et, avec le programme tools/build, concatène bbootsect, bsetup et compressed/bvmlinux.out pour obtenir bzImage (supprimez le « b » du début pour zImage). Ce qui a pour effet d'écrire à la fin du secteur d'amorçage des variables importantes comme setup_sects et root_dev.

II-B. Démarrage : aperçu

1. Le BIOS choisit le périphérique d'amorçage.
2. Le BIOS charge le secteur d'amorçage depuis le périphérique d'amorçage.
3. L'exécution du secteur d'amorçage charge setup, les routines de décompression et l'image compressée du noyau.
4. Le noyau est décompressé en mode protégé.
5. Les initialisations de bas niveau sont réalisées en assembleur.
6. Les initialisations de haut niveau sont réalisées en C.

II-C. Démarrage : BIOS POST

1. L'alimentation démarre le générateur d'horloge et envoie le signal #POWERGOOD sur le bus.
2. La ligne CPU #RESET est positionnée (Le CPU est maintenant en mode réel).
3. %ds=%es=%fs=%gs=%ss=0, %cs=0xFFFF0000,%eip = 0x0000FFF0 (ROM BIOS POST code).
4. Toutes les vérifications POST sont exécutées avec les interruptions désactivées.
5. IVT (Interrupt Vector Table ou table des vecteurs d'interruption) est initialisée à l'adresse 0.
6. La fonction BIOS de chargement du code d'amorçage est invoquée via int 0x19, avec %dl contenant le périphérique d'amorçage « numéro du disque ». Elle charge la piste 0, secteur 1 à l'adresse physique 0x7C00 (0x07C0:0000).

II-D. Démarrage : secteur d'amorçage et lancement

• Le secteur d'amorçage Linux (arch/i386/boot/bootsect.S),
• Le secteur d'amorçage de LILO (ou un autre chargeur d'amorçage), ou
• pas de secteur d'amorçage (loadlin, etc.)

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 */

/* 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

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 $gt;=
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.

1. positionnant %ds:%si sur $BOOTSEG:0 (0x7C0:0 = 0x7C00)
2. positionnant %es:%di sur $INITSEG:0 (0x9000:0 = 0x90000)
3. fixant le nombre de mots de 16 bits dans %cx (256 mots = 512 octets = 1 secteur)
4. réinitialisant le drapeau DF (direction) dans EFLAGS pour auto-incrémenter les adresses (cld)
5. avançant et copiant 512 octets (rep movsw)

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 -$gt; 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)

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:

II-E. Utilisation de LILO comme chargeur d'amorçage (bootloader)

1. La possibilité de choisir entre plusieurs noyaux Linux ou même plusieurs systèmes.
2. La possibilité de passer des paramètres en ligne de commande au noyau (il y a un correctif appelé BCP qui donne cette possibilité à bootsector+setup).
3. La possibilité de charger un noyau bzImage plus grand - jusqu'à 2.5 Mo au lieu de 1 Mo.

II-F. Initialisation de haut niveau

1. Initialisation des valeurs de segments (%ds = %es = %fs = %gs = __KERNEL_DS = 0x18).
2. Initialisation de la table des pages.
3. Activation de la pagination en positionnant le bit PG dans %cr0.
4. Initialisation à zéro de la BSS (sur du multiprocesseur, seul le premier processeur fait cela).
5. Copie des premiers 2 ko des paramètres d'amorçage (ligne de commande du noyau).
6. Vérification du type de CPU en utilisant EFLAGS et, si possible, cpuid, capable de détecter un 386 ou plus.
7. Le premier CPU appelle start_kernel(), tous les autres appellent arch/i386/kernel/smpboot.c:initialize_secondary() si ready=1, qui ne fait que recharger esp/eip et ne retourne pas.

1. Pose un verrou noyau global (c'est nécessaire afin qu'un seul CPU fasse l'initialisation).
2. Effectue les initialisations spécifiques à la plate-forme (analyse de la mémoire, copie une fois encore de la ligne de commande d'amorçage, etc.).
3. Affiche la « bannière » du noyau Linux contenant la version, le compilateur utilisé pour le construire, etc, jusqu'aux messages des tampons noyau. Son contenu est celui de la variable Linux_banner définie dans init/version.c et c'est la même chaîne qui est affichée par cat /proc/version.
4. Initialise les trappes (traps).
5. Initialise les IRQ (Interrupt ReQuest).
6. Initialise les données nécessaires à l'ordonnanceur (scheduler).
7. Initialise les données conservant le temps.
8. Initialise le sous-système d'IRQ logiciel (softirq).
9. Analyse les options de la ligne de commande d'amorçage.
10. Initialise la console.
11. Si le support des modules a été compilé dans le noyau, il initialise les capacités de chargement dynamique des modules.
12. Si la ligne de commande contient « profile= », il initialise les tampons nécessaires.
13. kmem_cache_init(), initialise la plupart du slab allocator (l'allocateur de tranche ?).
14. Active les interruptions.
15. Évalue la vitesse de ce CPU en BogoMips.
16. Appelle mem_init() qui calcule max_mapnr, totalram_pages et high_memory puis affiche la ligne « Memory: ... ».
17. kmem_cache_sizes_init(), finit l'initialisation du slab allocator.
18. Initialise les structures de données utilisées par procfs.
19. fork_init(), crée l'uid_cache, initialise max_threads en fonction de la quantité de mémoire disponible et configure RLIMIT_NPROC pour que init_task soit égal à max_threads/2.
20. Crée les divers caches de type slab nécessaires pour le système de fichiers virtuel, la mémoire virtuelle, le cache tampon, etc.
21. Si le support de la communication interprocessus (IPC System V) est compilé dans le noyau, initialise le sous-système IPC. Remarquez que pour shm System V, cela inclut de monter une instance du système de fichiers shmfs en interne (dans le noyau).
22. Si le support des quotas est compilé dans le noyau, crée et initialise un cache slab spécial pour eux.
23. Effectue les « vérifications de bogues (check for bugs) » spécifiques à l'architecture et, à chaque fois que possible, active les corrections pour les bugs processeur, bus, et cætera. La comparaison de plusieurs architectures révèle que « ia64 n'a pas de bugs » et que « ia32 en a quelques-uns », un bon exemple en est le « bug f00f » qui est testé seulement si le noyau est compilé pour un processeur inférieur au 686 et est alors corrigé.
24. Positionne un drapeau pour indiquer qu'un ordonnancement doit être effectué à la prochaine occasion et crée un thread noyau init() qui va « exec » execute_command si on a un paramètre de boot « init= », ou essayer d'exécuter /sbin/init, /etc/init, /bin/init, /bin/sh dans cet ordre ; si tout échoue, le noyau « panic » et émet la suggestion d'utiliser le paramètre « init= ».
25. Rentre dans une boucle inactive (idle), qui est un fil inactif (idle thread) avec un pid=0.

II-G. Amorçage multiprocesseur (SMP) sur x86

II-H. Libérer les données et le code d'initialisation

• __init - pour le code d'initialisation
• __initdata - pour les données

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

II-I. Traitement de la ligne de commande du noyau

1. LILO (ou BCP) traite la ligne de commande en utilisant les services clavier du BIOS et la stocke dans un endroit bien repéré de la mémoire physique, avec une signature signifiant qu'il y a une ligne de commande valide ici.
2. arch/i386/kernel/head.S en copie les 2 premiers k vers la page zéro.
3. arch/i386/kernel/setup.c:parse_mem_cmdline() (appelée par setup_arch(), elle même appelée par start_kernel()) copie 256 octets depuis la page zéro dans saved_command_line qui est affiché par /proc/cmdline. Cette même routine traite l'option « mem= » si elle est présente et fait les ajustements nécessaires aux paramètres de la VM.
4. Revenons à la ligne de commande traitée par parse_options() (appelé par start_kernel()) qui traite quelques paramètres « internes au noyau » (actuellement « init= » et l'environnement/arguments pour init) et passe chaque mot à checksetup().
5. checksetup() parcourt le code de la section ELF .setup.init et invoque chaque fonction, lui passant le mot précédent si celui-ci convient. Remarquez qu'en utilisant une valeur de retour de 0 depuis la fonction enregistrée via __setup(), il est possible de passer le même « variable=value » à plus d'une fonction avec « value » invalide pour l'une et valide pour l'autre. Jeff Garzik commente : « les hackers qui font cela s'en mordent les doigts :) ». Pourquoi ? Parce que c'est clairement spécifique à l'ordre d'édition des liens, i.e. un noyau lié dans un sens aura la fonction A appelée avant la fonction B, pour un autre ce sera le contraire, le résultat dépendant de l'ordre.

/*
 * 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

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);

III. Processus et gestion des interruptions

III-A. Structure de tâche et table des processus

/*
* 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;

# cat /proc/sys/kernel/threads-max 
32764
# echo 100000 $gt; /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

1. par une table de hachage, hachée sur le pid, et
2. par une liste circulaire doublement chaînée utilisant les pointeurs p-$gt;next_task et p-$gt;prev_task.

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

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-$gt;pid != pid; p = p-$gt;pidhash_next);
 
return p;
}

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

volatile long state;	/* -1 unrunnable, 0 runnable, $gt;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

1. TASK_RUNNING : signifie que la tâche « est censée être » dans la file d'exécution (runqueue). La raison pour laquelle elle peut ne pas être dans cette file, c'est que le marquage d'une tâche comme TASK_RUNNING et son placement dans la file n'est pas atomique. Il vous faut maintenir le verrou tournant en lecture-écriture runqueue_lock pour lire afin de rechercher dans la file d'exécution . Si vous faite cela vous verrez alors que toutes les tâches dans la file sont dans l'état TASK_RUNNING. Néanmoins, la réciproque n'est pas vraie pour les raisons expliquées précédemment. De la même façon, les pilotes peuvent se marquer eux mêmes (ou plutôt le contexte de processus dans lequel ils s'exécutent) comme TASK_INTERRUPTIBLE (ou TASK_UNINTERRUPTIBLE) et appeler schedule(), qui va alors les retirer de la file d'exécution (sauf s'il y a un signal en attente à leur destination, auquel cas, ils restent dans la file).
2. TASK_INTERRUPTIBLE : signifie que la tâche est endormie mais qu'elle peut être réveillée par un signal ou par l'expiration d'une alarme.
3. TASK_UNINTERRUPTIBLE : idem que TASK_INTERRUPTIBLE, sauf qu'elle ne peut pas être réveillée.
4. TASK_ZOMBIE : la tâche s'est terminée mais son état n'a pas été collecté par son parent (naturel ou par adoption - pas d'appel wait() du parent).
5. TASK_STOPPED : La tâche a été arrêtée, soit par un signal de contrôle des travaux (jobs) soit par ptrace(2).
6. TASK_EXCLUSIVE : Ce n'est pas un état à part entière mais il peut être combiné par un OU (OR) soit à TASK_INTERRUPTIBLE soit à TASK_UNINTERRUPTIBLE. Cela signifie que si cette tâche est endormie dans la file d'attente avec beaucoup d'autres, elle sera la seule à être réveillée, sans réveiller les autres tâches en attente, et provoquer un problème de « thundering herd ».

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) */

1. le dentry de la racine et le point de montage,
2. un dentry de la racine et un point de montage alternatif,
3. le dentry du répertoire de travail courant et le point de montage.

III-B. Création et terminaison des tâches et des threads noyau

• le(s) thread(s) idle (inutile/inactif),
• les threads noyau,
• les tâches utilisateur.

1. La variable locale retval est mise à -ENOMEM, car c'est la valeur à laquelle errno doit être positionnée si fork(2) échoue lors de l'allocation d'une nouvelle structure de tâche.
2. Si CLONE_PID est positionné dans clone_flags, alors on retourne une erreur (-EPERM), à moins que l'appelant soit le thread inactif (pendant l'amorçage seulement). Donc, un thread utilisateur normal ne peut pas passer CLONE_PID à clone(2) en espérant que ça marche. Pour fork(2), ce n'est pas pertinent, car clone_flags est positionné à SIFCHLD, ça n'est pertinent que lorsque do_fork() est appelé par sys_clone() qui passe alors clone_flags avec la valeur demandée depuis l'espace utilisateur.
3. current-$gt;vfork_sem est initialisé (il sera nettoyé plus tard dans l'enfant). C'est utilisé par sys_vfork() (l'appel système vfork(2) correspond à clone_flags = CLONE_VFORK|CLONE_VM|SIGCHLD) pour que le parent dorme jusqu'à ce que l'enfant fasse mm_release(), par exemple en résultat de l'exec()ution d'un autre programme ou en terminant par exit(2).
4. Une nouvelle structure de tâche est allouée en utilisant la macro spécifique à l'architecture alloc_task_struct(). Sur un x86 c'est juste un gfp à la priorité GFP_KERNEL. C'est la première raison pour laquelle l'appel système fork(2) doit dormir. Si cette allocation échoue, on retourne -ENOMEM.
5. Toutes les valeurs de la structure de tâche du processus courant sont copiées dans la nouvelle structure, en utilisant l'assignation de structure *p = *current. Peut-être que cela devrait être remplacé par un appel à memcopy ? Plus tard, les champs qui ne doivent pas être hérités par le fils seront positionnés aux valeurs correctes.
6. Un GROS verrou de noyau est posé car autrement le reste du code ne serait pas ré-entrant.
7. Si le parent a des ressources utilisateur (un concept d'UID, Linux est suffisamment flexible pour en faire une question plutôt qu'un fait), alors on vérifie si l'utilisateur dépasse la limite douce RLIMIT_NPROC - si c'est le cas, on échoue avec -EAGAIN, sinon, on incrémente le nombre de processus pour l'uid donné p-$gt;user-$gt;count.
8. Si le nombre de tâches du système dépasse la valeur paramétrable fixée par max_threads, on échoue avec -EAGAIN.
9. Si le binaire exécuté appartient à un domaine d'exécution modularisé, on incrémente le compteur de références du module.
10. L'enfant est marqué « non terminé » (p-$gt;did_exec = 0)
11. L'enfant est marqué comme ne pouvant pas être copié en zone d'échange (p-$gt;swappable = 0)
12. L'enfant est placé dans l'état de sommeil sans interruption (uninterruptible sleep), i.e. p-$gt;state = TASK_UNINTERRUPTIBLE (À FAIRE : Pourquoi c'est comme ça ? Je pense que ce n'est pas nécessaire - débarrassez vous en, Linus confirme que c'est inutile)
13. Les p-$gt;flags de l'enfant sont positionnés en fonction de la valeur de clone_flags; pour fork(2), ce sera p-$gt;flags = PF_FORKNOEXEC.
14. Le pid de l'enfant p-$gt;pid est fixé en utilisant un algorithme rapide dans kernel/fork.c:get_pid() (À FAIRE : le verrou tournant lastpid_lock peut être redondant tant que get_pid() est toujours appelé sous le gros verrou du noyau depuis do_fork(), donc je retire les arguments drapeau de get_pid(), le patch à été envoyé à Alan le 20/06/2000).
15. La suite du code dans do_fork() initialise le reste de la structure de tâche de l'enfant. Tout à la fin, cette structure est hachée dans la table de hachage pidhash et l'enfant est réveillé (À FAIRE : wake_up_process(p) positionne p-$gt;state = TASK_RUNNING et ajoute le processus dans la file d'exécution (runq), néanmoins on n'a probablement pas besoin de fixer p-$gt;state à TASK_RUNNING auparavant dans do_fork()). La partie intéressante consiste à mettre p-$gt;exit_signal à clone_flags & CSIGNAL, ce qui pour fork(2) signifie seulement SIGCHLD et fixer p-$gt;pdeath_signal à 0. Le pdeath_signal est utilisé quand un processus « oublie » son parent originel (en mourant) et peut être fixé/obtenu par le biais des commandes PR_GET/SET_PDEATHSIG de l'appel système prctl(2) (Vous pouvez dire que la façon dont la valeur de pdeath_signal est retournée via un argument pointant dans l'espace utilisateur dans prctl(2) est un peu idiote - mea culpa, une fois que Andries Brouwer a eu mis à jour la page man ça a été trop tard pour corriger;)

1. En faisant un appel système exit(2) ;
2. En recevant un signal qui la fait mourir par défaut ;
3. En étant forcée de mourir dans certaines conditions ;
4. En appelant bdflush(2) avec func == 1 (c'est spécifique à Linux, pour la compatibilité avec les vieilles distributions qui ont toujours la ligne « update » dans /etc/inittab - de nos jours le travail de mise à jour est fait par le thread noyau kupdate)

• utilise le verrou global du noyau (elle verrouille mais ne déverrouille pas),
• appelle schedule() à  la fin, qui ne retourne jamais,
• positionne l'état de la tâche à  TASK_ZOMBIE,
• informe tous les enfants en envoyant current-$gt;pdeath_signal, s'il n'est pas nul,
• informe le parent en envoyant current-$gt;exit_signal, qui en général est égal à  SIGCHLD,
• libère les ressources allouées par le fork, ferme les fichiers ouverts, etc,
• sur les architectures qui utilisent « lazy FPU switching » (ia64, mips, mips64) (À FAIRE : retirer l'argument « flags » pour les sparc, sparc64), fait tout ce qu'il faut selon le matériel pour que le propriétaire du FPU (si celui-ci appartient à  la tâche courante) devienne « none » (personne).

III-C. L'ordonnanceur Linux

• p-$gt;need_resched : ce champ est positionné si schedule() doit être appelé « à la prochaine occasion ».
• p-$gt;counter : nombre de tops d'horloge restant dans cette tranche d'ordonnancement, décrémenté par un chronomètre. Quand ce champ devient inférieur ou égal à  zéro, il est remis à  zéro et p-$gt;need_resched est positionné. Cette variable est parfois appelée « dynamic priority » d'un processus car cette priorité change par elle-même.
• p-$gt;priority : priorité statique du processus, elle ne peut être changée que par des appels systèmes répertoriés comme nice(2), sched_setparam(2) POSIX.1b ou setpriority(2) 4.4BSD/SVR4.
• p-$gt;rt_priority : priorité temps réel
• p-$gt;policy : politique d'ordonnancement, spécifie à  quelle classe d'ordonnancement la tâche appartient. Les tâches peuvent modifier leur classe d'ordonnancement en utilisant l'appel système sched_setscheduler(2). Les valeurs reconnues sont SCHED_OTHER (processus UNIX traditionnel), SCHED_FIFO (processus FIFO temps réel POSIX.1b) et SCHED_RR (processus temps réel POSIX utilisant l'algorithme round-robin). On peut aussi faire SCHED_YIELD OU l'une de ces valeurs pour indiquer que c'est le processus qui décide de libérer le CPU, par exemple en invoquant l'appel système sched_yield(2). Un processus FIFO (premier arrivé, premier servi) temps réel tournera jusqu'à ce que : a) il soit bloqué par une entrée/sortie, b) il libère explicitement le CPU ou c) il soit préempté par un autre processus temps réel avec une valeur de priorité p-$gt;rt_priority plus importante. Pour SCHED_RR c'est la même chose que pour SCHED_FIFO, sauf que lorsque la tranche de temps expire il retourne à  la fin de la file d'exécution (runqueue).

1. Si current-$gt;active_mm == NULL alors quelque chose est faux. Le processus courant, même un thread noyau (current-$gt;mm == NULL) doit avoir un p-$gt;active_mm valide en permanence.
2. S'il y a quelque chose à traiter dans la file de tâches tq_scheduler, le faire maintenant. La file de tâches fournit au noyau un mécanisme pour ordonnancer l'exécution ultérieurs de fonctions. On détaillera cela par la suite.
3. Initialiser les variables locales prev et this_cpu respectivement pour la tâche et le CPU courants.
4. Vérifier si schedule() a été appelé par le gestionnaire d'interruption (suite à  un bug) et panique si c'est le cas.
5. Libérer le verrou global du noyau.
6. S'il y a un travail à réaliser par IRQ logiciel (softirq), le faire maintenant.
7. Initialiser le pointeur local struct schedule_data *sched_data pour le faire pointer sur la zone des données d'ordonnancement par CPU (cacheline-aligné pour éviter le cacheline ping-pong) qui contient la valeur TSC de last_schedule et le pointeur vers la dernière structure de tâche ordonnancée (À FAIRE : sched_data n'est utilisé que pour le multiprocesseur (SMP) alors pourquoi init_idle() l'initialise-t-il aussi sur de l'uniprocesseur ?).
8. Un verrou tournant runqueue_lock est posé. Remarquez que nous utilisons spin_lock_irq() car dans schedule() on est sûr que les interruptions sont activées. Par conséquent, quand on déverrouille runqueue_lock, il n'y a qu'à  les réactiver au lieu de sauver/restaurer eflags (variante spin_lock_irqsave/restore).
9. La machine d'état de la tâche : si la tâche est dans un état TASK_RUNNING, on n'y touche pas ; si elle est dans un état TASK_INTERRUPTIBLE et qu'un signal est suspendu elle est placée dans l'état TASK_RUNNING. Dans tous les autres cas elle est effacée de la file d'exécution.
10. next (suivant - le meilleur candidat à  l'ordonnancement) prend pour valeur la tâche idle de notre CPU. Néanmoins, la qualité de ce candidat est mise à  une valeur très basse (-1000), dans l'espoir de trouver un meilleur candidat.
11. Si la tâche prev (courante) est dans un état TASK_RUNNING, alors la qualité courante est fixée à sa qualité et cette tâche est marquée comme meilleur candidat à ordonnancer que la tâche idle.
12. Maintenant la queue d'exécution est examinée et les qualités de chaque processus susceptible d'être ordonnancé sur ce CPU sont comparées à la valeur courante ; le processus qui a la qualité la plus haute gagne. Maintenant le concept de « susceptible d'être ordonnancé sur ce CPU » doit être éclairci : sur de l'UP, chaque processus de la queue d'exécution est éligible pour être ordonnancé; sur du multiprocesseur, seuls les processus qui ne sont pas en cours d'exécution sur un autre CPU sont éligibles pour être ordonnancés sur ce CPU. La qualité est calculée au moyen d'une fonction appelée goodness(), qui fixe très haut la qualité des processus temps réel (1000 + p-$gt;rt_priority), une valeur supérieure à 1000 garantit qu'aucun processus SCHED_OTHER ne peut gagner ; donc ils ne sont en compétition qu'avec d'autres processus temps réel ayant une plus grande priorité p-$gt;rt_priority. La fonction goodness retourne 0 si la tranche de temps (process time slice) du processus (p-$gt;counter) est terminée. Pour des processus non temps réel, la valeur initiale de la qualité est fixée à  p-$gt;counter - de cette façon, le processus a moins de chances d'avoir le CPU s'il l'a déjà eu récemment, i.e. les processus interactifs sont plus favorisés que les mangeurs de CPU. La constante spécifique à  l'architecture PROC_CHANGE_PENALTY essaie d'implémenter « l'affinité CPU » (i.e. donner l'avantage à  un processus du même CPU). Cela donne aussi un léger avantage aux processus ayant mm pointant sur le active_mm courant ou aux processus sans espace d'adressage (utilisateur), i.e. les threads noyau.
13. si la valeur courante de la qualité est 0 alors la liste complète des processus (pas seulement ceux de la queue d'exécution!) est examinée et leurs priorités dynamiques sont recalculées par un algorithme simple : recalculate: { struct task_struct *p; spin_unlock_irq(&#38;runqueue_lock); read_lock(&#38;tasklist_lock); for_each_task(p) p-$gt;counter = (p-$gt;counter $gt;$gt; 1) + p-$gt;priority; read_unlock(&#38;tasklist_lock); spin_lock_irq(&#38;runqueue_lock); } Remarquez que l'on enlève le verrou runqueue_lock avant de recalculer. La raison en est que nous devons traiter l'ensemble des processus, ce qui peut prendre un long moment, durant lequel schedule() peut être appelée sur un autre CPU et choisir un processus avec une qualité satisfaisante pour ce CPU, pendant que nous sur ce CPU on est forcé de recalculer. Ok, de l'aveu général c'est un inconvénient parce que pendant qu'on (sur ce CPU) choisit un processus avec la meilleure qualité, schedule() s'exécutant sur un autre CPU peut recalculer les priorités dynamiques.
14. A partir de ce moment on est certain que next pointe sur la tâche à  ordonnancer, donc on initialise next-$gt;has_cpu à  1 et next-$gt;processor à  this_cpu. Le runqueue_lock peut être levé.
15. Si on rebascule sur la même tâche (next == prev) alors on peut simplement réacquérir le verrou global du noyau et retourner, sans avoir à  traiter tout ce qui concerne le matériel (registres, pile etc.) ni ce qui est lié à  la VM (changer le répertoire de page, recalculer active_mm etc.).
16. La macro switch_to() est spécifique à  l'architecture. Sur un i386, cela concerne a) la gestion du FPU, b) la gestion de la LDT, c) le rechargement des registres de segment, d) la gestion de la TSS et e) le rechargement des registres de déboguage.

III-D. Implémentation des listes chaînées Linux

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)-$gt;next = (ptr); (ptr)-$gt;prev = (ptr); \
} while (0)

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

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

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-$gt;s_files.next; p != &sb-$gt;s_files; p = p-$gt;next) {
     struct file *file = list_entry(p, struct file, f_list);
     do something to 'file'
}

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-$gt;active_mm);
        if (weight $gt; c)
            c = weight, next = p;
    }
}

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

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

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

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

III-E. Les files d'attente (Wait Queues)

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);
}

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-$gt;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-$gt;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-$gt;state = TASK_RUNNING;
	remove_wait_queue(&rtc_wait, &wait);
	return retval;
}

1. On déclare un élément de file d'attente pointant sur le contexte du processus courant.
2. On ajoute cet élément à  la file d'attente rtc_wait.
3. On marque le contexte courant comme TASK_INTERRUPTIBLE ce qui signifie qu'il ne sera pas réordonnancé à  la fin de son prochain temps de sommeil.
4. On vérifie s'il y a des données disponibles ; s'il y en a, on s'interrompt, on copie les données dans le tampon utilisateur, on se marque TASK_RUNNING, on se retire nous même de la file d'attente et on retourne.
5. S'il n'y a pas encore de données, on regarde si l'utilisateur a spécifié une entrée/sortie non bloquante et si oui on échoue avec EAGAIN (qui est la même chose que EWOULDBLOCK)
6. Nous regardons également s'il y a un signal suspendu et si tel est le cas on demande aux « couches supérieures » de relancer l'appel système si nécessaire. Par « si nécessaire » je pense aux détails de la disposition du signal tels que spécifiés lors de l'appel système sigaction(2).
7. Alors on « bascule hors de la tâche (switch out) », i.e. on s'endort, jusqu'à  ce qu'on soit réveillé par la routine d'interruption. Si on ne s'est pas marqué nous même comme TASK_INTERRUPTIBLE, alors l'ordonnanceur peut nous ordonnancer avant que les données soient disponibles, ce qui cause des traitements inutiles.

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;
}

III-F. Les chronomètres du noyau (timers)

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

III-G. Bouts de listes (Bottom Halves)

• void init_bh(int nr, void (*routine)(void)) : installe le gestionnaire de bottom half pointé par l'argument routine à  l'emplacement nr. Les emplacements sont énumérés dans include/linux/interrupt.h sous la forme XXXX_BH, i.e. TIMER_BH ou TQUEUE_BH. Typiquement, une fonction d'initialisation d'un sous-système (init_module() pour les modules) installe les bottom half requis en utilisant cette fonction.
• void remove_bh(int nr) : fait le contraire de init_bh(), i.e. elle désinstalle le bottom half installé à  l'emplacement nr. Il n'y pas de vérification d'erreur effectuée ici, alors, par exemple remove_bh(32) va faire paniquer (panic/Oops) le système. Typiquement, une routine de nettoyage d'un sous-système (cleanup_module() pour modules) utilise cette fonction pour libérer son emplacement qui pourra être réutilisé plus tard par un autre sous-système. (À FAIRE : ne serait il pas bien d'avoir un /proc/bottom_halves listant tous les bottom halves enregistrés sur le système ? Ce qui signifie que global_bh_lock doit être mis en lecture/écriture, évidemment)
• void mark_bh(int nr) : marque le bottom half à  l'emplacement nr pour exécution. Typiquement, une routine d'interruption marquera son bottom half (d'où le nom!) pour exécution à  un « moment plus sûr ».

III-H. Les files de tâches (Task Queues)

1. Il y en a seulement un certain nombre (32).
2. Chaque bottom half peut être associé à  un seul gestionnaire.
3. Les bottom halves sont dévorées par le verrou tournant mis pour qu'elles ne puissent pas bloquer.

1. tq_timer : la file de tâche des chronomètres, s'exécute à chaque interruption de chronomètre et quand on libère un périphérique tty (fermeture ou libération d'un périphérique terminal à demi ouvert). Tant que le gestionnaire de chronomètre s'exécute dans un contexte d'interruption, la tâche tq_timer s'exécute aussi dans un contexte d'interruption et donc ne peut pas bloquer.
2. tq_scheduler : la file de tâche de l'ordonnanceur, exécutée par l'ordonnanceur (et aussi quand on ferme un périphérique tty, comme tq_timer). Comme l'ordonnanceur a été exécuté dans le contexte du processus étant réordonnancé, les tâches de tq_scheduler peuvent faire ce quelles veulent, i.e. bloquer, utiliser les données du contexte processus (mais pourquoi voudraient-elles le faire), et cætera.
3. tq_immediate : c'est un vrai bottom half IMMEDIATE_BH, donc les pilotes peuvent queue_task(task, &tq_immediate) (mettre une tâche dans la file) puis mark_bh(IMMEDIATE_BH) (la marquer) pour être exécutée dans un co