Pour cette nouvelle édition du Kernel Corner, nous vous proposons trois brèves dont la deuxième est écrite par Frédéric Raynal (rédac chef de MISC). Il nous présente un module qu’il a développé à des fins pédagogiques pour découvrir le fonctionnement de la pagination. La dernière brève développe une analyse sur les problèmes liés aux crashs des drivers affectant la stabilité du système et les solutions proposées et disponibles pour y faire face. Pour la première brève, le fonctionnement de l’infrastructure de gestion unifiée des événements, Kevent, est expliqué.

Kevent : mécanisme générique de gestion des événements

Introduction

Kevent est un mécanisme générique de gestion d’événements créé par Evgeniy Polyakov. Au travers d’une interface unifiée permettant la gestion de toutes sortes d’événements (socket, poll/select, timer, signal, etc.), il permet aux programmes utilisateurs y faisant appel, d’être averti lors de leur survenance. Il a été conçu dans le même esprit que les completion ports de MS Windows ou que l’infrastructure kqueue de FreeBSD/OS X. En utilisant un seul appel système, un thread peut récupérer tous les types d’événements que le noyau est capable de générer. Cela, à la place des anciennes interfaces qui n’autorisent que la réception de types spécifiques d’événements (par exemple : l’expiration de timers, l’arrivée d’un nouveau message dans une file, etc.).
Son utilisation passe par la définition de nouveaux appels système. Le projet en est, lors de l’écriture de ces lignes, à sa 35ème révision ! Avant d’être incluse dans la mainline, il est nécessaire que l’API soit irréprochable, car alors il ne sera plus possible de la changer (étant liée à l’espace utilisateur). Ulrich Drepper, mainteneur de la glibc, a participé activement à la critique de l’API et des fonctionnalités. Ainsi, la version actuelle est très proche de la maturité nécessaire à l’inclusion dans la mainline.
Kevent supporte la définition d’événements déclenchés par front ou par niveau. Dans certaines situations, il est semblable à poll/epoll tout en étant plus rapide et supportant bien mieux le passage à l’échelle. Il a été conçu pour travailler avec quasiment n’importe quel type d’événement (par exemple les signaux POSIX ;).

Descripteur d’un événement : structure ukevent

Tout d’abord jetons un œil au descripteur d’un événement au niveau utilisateur. Cette structure va servir lors de l’ajout, de la modification ou de la suppression d’une requête au noyau sur la notification d’un type d’événement, mais également pour signifier qu’un événement a été consommé (c.-à-d. utilisé) par l’application.

struct ukevent
{
  /* Identifiant de cette requête, ex : numéro
     de socket, descripteur de fichier, etc. */
  struct kevent_id        id;
  /* Type de l’événement, ex : KEVENT_SOCK,
     KEVENT_INODE, KEVENT_TIMER, etc. */
  __u32                   type;
  /* L’événement lui-même, ex : SOCK_ACCEPT,
     INODE_CREATED, TIMER_FIRED, etc. */
  __u32                   event;
  /* Flags propre à chaque événement et définis
     lors de la requête */
  __u32                   req_flags;
  /* Flags propre à chaque événement et défini
     par le noyau
   * ex : KEVENT_REQ_ONESHOT, KEVENT_REQ_READY, etc. */
  __u32                   ret_flags;
   /* Données retournées par l’événement. Au choix du
     responsable du déclenchement de l’événement. */
  __u32                   ret_data[2];
   /* Données de l’utilisateur, non utilisée, juste
     copiées depuis et vers l’espace utilisateur.
   */
  union {
          __u32           user[2];
          void            *ptr;
        };
};

Nous ne rentrerons pas, par la suite, dans le détail de tous les membres de cette structure. Nous expliquerons l’infrastructure Kevent vue depuis l’espace utilisateur et, ensuite, nous relierons les éléments clés aux activités correspondantes se déroulant au sein du noyau. Cette dernière étape est à voir comme une introduction pour le lecteur souhaitant approfondir le sujet.

API de Kevent

L’interaction avec le noyau pour effectuer un ajout, une modification, une suppression de requête sur événement, ou bien signifier qu’un événement est prêt (ce qui permet de réveiller un ou plusieurs threads en attente sur cet événement), passe par l’utilisation de la fonction kevent_ctl. Avant d’appeler cette dernière, il est nécessaire de demander au noyau de créer une structure pour cataloguer les futurs événements que nous souhaitons surveiller. Pour cela, la première méthode est d’ouvrir le fichier /dev/kevent. Ainsi, un descripteur propre à l’application (dont l’élément principal est une liste) est créé par le noyau et un identifiant permettant le dialogue avec le noyau est retourné par l’appel système open. Une autre méthode est également proposée pour répondre à certaines situations que nous allons bientôt expliquer.

int kevent_ctl(int fd,
               unsigned int cmd,
               unsigned int num,
               struct ukevent *arg)

Cet appel système est celui qui nous permet de gérer nos requêtes de notification sur événements. Ces paramètres sont les suivants :

• fd : Il s’agit du descripteur de fichier (l’identifiant), correspondant à la file d’événement Kevent utilisée par l’application.
• cmd : Il s’agit de la commande à exécuter. Les choix possibles sont : KEVENT_CTL_ADD, KEVENT_CTL_REMOVE, KEVENT_CTL_MODIFY, KEVENT_CTL_READY pour respectivement, ajouter, supprimer, modifier une requête de notification ou marquer une notification comme étant prête afin de réveiller les threads l’attendant.
• num : Il s’agit du nombre de requêtes qui sont soumises lors de l’appel.
• arg : Nous fournissont dans cet argument un pointeur sur les structures ukevent, définissant nos requêtes.

Après avoir ajouté des requêtes de notification sur certains types d’événements via l’utilisation de kevent_ctl, le noyau va récupérer les événements émis par les sous-systèmes correspondants et les placer dans une structure struct kevent_user accessible seulement depuis l’espace noyau et définie pour chaque utilisateur. Nous revenons par la suite sur cette structure.
Afin de récupérer des événements depuis l’espace utilisateur, deux solutions sont proposées. La première est une version synchrone qui va donc déclencher l’écriture des événements qui se produisent lors de l’appel. Dans la seconde version, qui est asynchrone, l’utilisateur va récupérer les événements au travers d’un buffer qui est rempli progressivement par le noyau. Cette dernière méthode est préconisée pour les applications nécessitant des performances optimales.

Interface synchrone

L’interface synchrone est la plus simple à utiliser, mais aussi la moins performante. Elle passe par l’utilisation de la fonction suivante retournant le nombre d’événements copiés et qui peut être utilisée de façon bloquante ou non via le paramètre timeout :

int kevent_get_events(int ctl_fd,
                      unsigned int min_nr,
                      unsigned int max_nr,
                      struct timespec timeout,
                      struct ukevent *buf,
                      unsigned flags)

• ctl_fd : Comme précédemment, il s’agit de l’identifiant du descripteur de la file Kevent.
• min_nr : Le nombre minimal d’événements à renvoyer pour que la fonction retourne à l’appelant.
• max_nr : Le nombre de structures ukevent que nous fournissons via le tampon mémoire buf
• timeout : Le temps d’attente avant de retourner à l’appelant si moins de min_nr événements ont été produits.
• buf : Le pointeur sur la table des ukevent
• flags : Ce drapeau peut prendre actuellement seulement la valeur KEVENT_FLAGS_ABSTIME pour signifier au noyau que la valeur de timeout est une valeur de temps absolue. Par défaut (flags à NULL), le timeout est une valeur définie relativement à la date actuelle.

Interface asynchrone

L’interface asynchrone est un peu plus complexe à mettre en place au niveau utilisateur. En effet, elle passe par l’initialisation d’un buffer au niveau de l’espace utilisateur dans lequel le noyau copie les événements produits depuis sa propre structure interne (dans l’espace noyau), en faisant attention à ne pas écraser les événements non encore consommés. Ainsi, l’application doit appeler la fonction kevent_commit afin de signifier au noyau où en est l’état de son buffer.
Le descripteur de ce buffer, une structure kevent_ring, est défini comme ci-dessous. Il s’agit d’une table circulaire (c.-à-d. qu’une fois arrivé à la fin de la table, la première entrée est de nouveau utilisée) dont la taille est au choix de l’application. Le membre ring_kidx correspond à l’index dans la table utilisée par le noyau pour y écrire un prochain événement. Le membre ring_over sert, quant à lui, à conserver le nombre de tours déjà effectués dans la table circulaire, afin que le noyau et l’application soient en phase sur l’état du buffer, avant que cette dernière ne marque des événements comme étant consommés.

struct kevent_ring
{
  unsigned int ring_kidx, ring_over;
  struct ukevent event[0];
}

Après la déclaration d’une telle structure, la fonction suivante est appelée par l’application. Elle fournit en retour un identifiant unique, correspondant à la structure interne du noyau y étant associée (la structure struct kevent_user) et nécessaire aux futures interactions entre l’utilisateur et le noyau. Cet identifiant a exactement le même rôle que celui fourni lors de l’ouverture de /dev/open.

int kevent_init(struct kevent_ring *ring,
                unsigned int ring_size,
                unsigned int flags);

• ring : Pointeur sur le tampon circulaire ;
• ring_size : Taille du tampon circulaire en nombre d’événements ;
• flags : Comme toutes les fonctions précédentes, seul le drapeau KEVENT_FLAGS_ABSTIME est reconnu.

Pour récupérer à présent les événements, nous utilisons la fonction suivante qui retourne le nombre d’événements copiés dans le tampon circulaire :

 int kevent_wait(int ctl_fd,
                unsigned int num,
                struct timespec timeout,
                unsigned int flags)

• ctl_fd : Comme précédemment, il s’agit de l’identifiant du descripteur de la file Kevent ;
• num : Nombre d’événements maximal à écrire dans le tampon circulaire ;
• timeout : Le temps d’attente maximal avant de retourner à l’appelant, pour que de la place se libère dans la file kevent ;
• flags : Comme toutes les fonctions précédentes, seul le drapeau KEVENT_FLAGS_ABSTIME est reconnu.

Pour renseigner le noyau sur le fait qu’un événement a été consommé, l’utilisateur appelle la fonction suivante qui retourne le nombre de kevent enregistrés comme étant consommés :

 int kevent_commit(int ctl_fd,
                  unsigned int new_uidx,
                  unsigned int over);

• ctl_fd : Comme précédemment, il s’agit de l’identifiant du descripteur de la file Kevent
• new_uidx : L’index relatif à l’événement consommé ;
• over : Compteur de cycle dans le tampon circulaire pour la valeur new_uidx donnée (correspond au membre ring_over de la structure kevent_ring).

Dans le noyau

Pour chaque utilisateur de Kevent, le noyau initialise une structure du type kevent_user. Cette structure embarque un arbre binaire auto-équilibré de type red black tree pour le stockage des événements (le membre kevent_root pointe sur sa racine), ainsi qu’une liste doublement chaînée (cf. KC 86) pour accéder facilement aux événements qui sont prêts (via le membre ready_list). Notons que la file d’attente wait dans la structure est utilisée pour stocker temporairement les processus en attente sur un événement en dehors des listes de l’ordonnanceur. Finalement, remarquons que le tampon circulaire de l’espace utilisateur est disponible via le pointeur pring (la macro __user est utilisée, car l’adresse est à interpréter dans l’espace d’adressage virtuel propre à l’application et non celui du noyau).

struct kevent_user
{
  struct rb_root          kevent_root;
  spinlock_t              kevent_lock;
  /* Nombre de kevent enregistrés */
  unsigned int            kevent_num;
  /* Liste des kevents prêt */
  struct list_head        ready_list;
  /* Nombre de kevents prêt */
  unsigned int            ready_num;
  /* Utilisé pour la protection de la liste
     ready_list (cf. KC 87 sur les spinlocks) */
  spinlock_t              ready_lock;
  /* Mutex pour se protéger des manipulations
     simultanées de la structure kevent_user */
  struct mutex            ctl_mutex;
  /* File d’attente jusqu’à ce que les événements
     soient prêts */
  wait_queue_head_t       wait;
  int                     need_exit;
  /* Compteur incrémenté pour chaque nouveau kevent */
  atomic_t                refcnt;
  /* Mutex pour la protection sur l‘accès depuis le
     noyau au tampon circulaire qui est en espace
     utilisateur */
  struct mutex            ring_lock;
  /* Index, taille, etc. */
  unsigned int     kidx, uidx, ring_size, ring_over, full;
  /* Pointeur vers le tampon circulaire
     en espace utilisateur */
  struct kevent_ring __user *pring;
   /* Utilisé pour les échéances donné avec une date
     et non une valeur relative */
  struct hrtimer          timer;
   /* Utilisé uniquement pour des événements privés de
     l’espace utilisateur s’ils ont été définis */
  struct kevent_storage   st;
};

Les événements stockés dans la structure précédente ne sont pas des structures struct ukevent. En fait, la représentation interne d’un événement au sein du noyau est une structure struct kevent contenant le ukevent correspondant à la requête émise par l’utilisateur.

struct kevent
{
  /* RCU Utilisé pour la libération de la structure
   * (cf. KC 89 pour une introduction sur ce moyen
   * de synchronisation) */
  struct rcu_head         rcu_head;
  struct ukevent          event;
  /* Pour la protection sur la modification de la structure */
  spinlock_t              ulock;
  /* Entrée dans le red black tree du kevent_user */
  struct rb_node          kevent_node;
  struct list_head        storage_entry;
  struct list_head        ready_entry;
  u32                     flags;
  /* Lien sur la structure propre à l’utilisateur */
  struct kevent_user      *user;
       struct kevent_storage   *st;
       struct kevent_callbacks callbacks;
  /* Données privées pour différent type de stockage.
   * Au choix du sous-système relatif à l’événement
   * concerné.
   */
  void                    *priv;
};

Notons que les membres storage_entry et ready_entry ne sont pas employés ensembles. En effet, s’il s’agit d’un événement classique, le membre ready_entry est utilisé pour la liaison avec la liste correspondante (ready_list) présente dans la structure kevent_user ; sinon, il s’agit d’un événement privé et l’autre membre est utilisé, auquel cas des données privées peuvent être utilisées par le sous-système via le membre priv.
Finissons en mentionnant le membre callbacks qui est une structure contenant trois pointeurs sur des fonctions. Chacune d’elles sert dans une situation bien précise. Une première est exécutée lorsque l’événement correspondant se produit, une autre lors du chaînage de l’événement (c.-à-d. de la structure) et la dernière lorsque la structure est enlevée de la file.

Sous-systèmes du noyau convertis à Kevent

Dans la version 35 du patch, huit sous-systèmes ont été convertis à l’utilisation de Kevent. Au niveau des sockets, Kevent permet de déclencher rapidement les notifications pour chaque commande send, recv ou accept, pour une socket donnée. Aussi, les méthodes poll/select de tous les drivers peuvent être utilisées au travers de Kevent. De même, au niveau des pipes, la notification peut s’effectuer sur la survenance des événements send/recv ou pipe/fifo. Les timers ne sont pas oubliés, et Kevent rend compte également de l’utilisation des high-resolution timers. Notons également le support de l’infrastructure des signaux par Kevent, rendant possible l’envoi des signaux au travers de la file d’événements de Kevent. Dans le même esprit, l’événement d’expiration des timers POSIX peut être véhiculé au travers de la file Kevent. Une autre fonctionnalité permet la définition de n’importe quel événement privé au niveau utilisateur et ensuite de le valider au moyen de la commande kevent(KEVENT_READY).
Finalement, le dernier apport à Kevent a été l’implémentation de primitives asynchrones d’entrées/sorties (AIO) supportant l’infrastructure de Kevent. Ainsi les appels système aio_sendfile et aio_sendfile_path ont été définis et apportent un gain en performance significatif face à l’utilisation de sendfile qui est synchrone.

Conclusion

Pour les plus intéressés, le site du projet est accessible via http://tservice.net.ru/~s0mbre/old/?section=projects&item=kevent. Vous y trouverez les dernières nouveautés concernant Kevent, une documentation en cours d’écriture, ainsi que des benchmarks. Aussi, la mise à disposition d’exemples d’utilisation est prévue lorsque l’API sera complètement stabilisée, c’est-à-dire lorsque Kevent sera inclus dans la mainline, ce qui semble être un événement proche ;)

kpage, un module pour explorer la mémoire

Kpage [1] est un petit module développé à l’occasion pour expliquer le comportement du bit NX sur les architectures 64 bits. Il permet de se promener dans l’organisation des pages mémoires. Pour y parvenir, on utilise plusieurs "objets" et "techniques" liés à la programmation noyau : voici ce que propose d’explorer cet article.
Ce petit module de rien du tout touche en réalité à plusieurs choses amusantes :

• d’abord son objectif est d’afficher la structure des pages jusqu’au descripteur, voire le contenu de ces pages : il s’agit donc de manipuler directement la mémoire, mieux vaut éviter de se planter, ce serait fatal ;
• il faut pouvoir accéder à ces informations depuis l’espace utilisateur : on crée donc une sous-arborescence dans le /proc pour cela ;
• on souhaite pouvoir changer le PID et l’adresse à explorer sans avoir à charger/décharger le module à chaque fois.

La compilation facile avec kbuild

La compilation des modules est devenue très simple depuis l’adoption de kbuild.

$ cat Makefile
EXTRA_CFLAGS := -D_X86_64_
#EXTRA_CFLAGS := -D_X86_32_
ifneq ($(KERNELRELEASE),)
obj-m   := kpage.o
kpage-y := kparam.o pagetable.o registers.o \
           xdump.o rdump.o kpage_core.o
else
KDIR := /lib/modules/$(shell uname -r)/build
PWD := $(shell pwd)
default:
        $(MAKE) -C $(KDIR) SUBDIRS=$(PWD) modules
clean:
        rm -rf *~ *o *.mod.c .*cmd .tmp_versions
endif

En gros, il faut juste retenir que obj-m indique que nous allons construire un module, et kpage-y liste les fichiers nécessaires pour ça. Ensuite, la ligne avec $(MAKE) fait tout le travail pour nous : ça appelle le système kbuild, qui initialise tout ce qui est nécessaire, puis ça revient dans le répertoire courant pour construire ce qu’on lui demande :

raynal@batman:~/MISC/kpage/kpage$ make
make -C /lib/modules/2.6.18-3-amd64/build
SUBDIRS=/home/raynal/MISC/kpage/kpage modules
make[1]: Entering directory `/usr/src/linux-headers-2.6.18-3-amd64’
  CC [M]  /home/raynal/MISC/kpage/kpage/kparam.o
  CC [M]  /home/raynal/MISC/kpage/kpage/pagetable.o
  CC [M]  /home/raynal/MISC/kpage/kpage/registers.o
  CC [M]  /home/raynal/MISC/kpage/kpage/xdump.o
  CC [M]  /home/raynal/MISC/kpage/kpage/rdump.o
  CC [M]  /home/raynal/MISC/kpage/kpage/kpage_core.o
  LD [M]  /home/raynal/MISC/kpage/kpage/kpage.o
  Building modules, stage 2.
  MODPOST
  CC      /home/raynal/MISC/kpage/kpage/kpage.mod.o
  LD [M]  /home/raynal/MISC/kpage/kpage/kpage.ko
make[1]: Leaving directory `/usr/src/linux-headers-2.6.18-3-amd64’

Du côté des sources, plus besoin de déclarations étranges signalant qu’il s’agit de code noyau ou d’un module, tout cela est pris en charge par kbuild.

Se promener dans les pages mémoires

Il ne s’agit pas ici d’un cours sur la mémoire, mais de voir les structures et les méthodes de programmation associées. Donc, nous rappellerons juste que la pagination est un mécanisme qui intervient après la segmentation. La segmentation n’est pas ou peu utilisée, et repose sur le modèle flat en général, c’est-à-dire qu’à une adresse logique correspond une adresse linéaire, à une transformation linéaire près. Le modèle flat fait en sorte que cette correspondance soit directe (ou presque). Nous n’en parlerons donc plus.
L’objectif de la pagination est de convertir cette adresse linéaire en une adresse physique, c’est-à-dire retrouver l’endroit où se cachent les octets correspondant à cette adresse. Pour cela, cette adresse est décomposée en plusieurs blocs, chaque bloc étant en réalité un index dans un tableau.
Linux supporte un nombre non négligeable d’architectures. Manque de chance, certaines utilisent une pagination à 4 niveaux (x86_64 comme nous le verrons par la suite), d’autres à 2 niveaux (IA32 en mode normal) et d’autres, pas du tout de pagination (puisqu’elle est optionnelle). Histoire de se simplifier la vie, les développeurs ont donc considéré qu’il y avait toujours 4 niveaux de pagination (enfin, quand pagination il y a). La seule chose qu’ils changent, ce sont les macros permettant de passer d’un niveau au suivant.
Les 4 niveaux sont donc : Page Global Directory (PGD), Page Upper Directory (PUD), Page Middle Directory (PMD) et, enfin, Page Table Entry (PTE). Il faut voir chacune de ces structures comme des tableaux dont les cases pointent sur un répertoire du niveau suivant. Ainsi, une entrée du PGD pointe sur l’élément 0 d’un PUD. Sur x86_64, il y a au plus 512 entrées dans le PGD, mais toutes ne sont pas utilisées en même temps. En gros, celles utilisées vont permettre de découper la mémoire pour les régions allouées (noyau, pile, tas, les bibliothèques, le binaire, etc.). Une entrée du PGD nous conduit à un PUD, composé lui aussi de 512 entrées sur x86_64. Chaque entrée du PUD pointe sur un PMD, et ainsi de suite. Au dernier niveau, chaque entrée PTE contient un descripteur de la page physique, descripteur qui fournit de précieuses informations sur la page physique :

• Le niveau de privilège requis pour y accéder, rien à voir avec les rings de la segmentation, il n’y a là que deux niveaux : user ou superviser, qui correspondent respectivement au mode utilisateur ou noyau.
• La page est-elle accessible en lecture/écriture ou lecture seule (bit RW) ?
• La page a-t-elle été modifiée depuis qu’elle est en mémoire (bit dirty) ?
• La page est-elle présente en mémoire (bit present) ?
• Etc.

La pagination permet d’éviter la redondance des pages en mémoire. Nous verrons comment/pourquoi par la suite, mais le principe est que si une bibliothèque, par exemple, est utilisée par plusieurs processus, ses instructions seront dans quelques pages physiques, une bonne fois pour toute. Ensuite, les processus qui en ont besoin les utiliseront, sans doute à des adresses virtuelles différentes, mais qui pointeront toutes vers ces mêmes pages physiques.
Du coup, on réalise que tout ce qui s’exécute quand la pagination est activée a besoin de son propre environnement de pagination. Et comme nous l’avons dit, la base, c’est le PGD. Pour cela, la convention veut que le registre CR3 contienne l’adresse du PGD (sur x86) : chaque tâche possède son propre PGD, et à chaque changement de contexte, le registre CR3 est mis à jour. Mais il est une "tâche" à laquelle on ne pense pas systématiquement : le noyau. Lui aussi possède son propre PGD, et donc les pages physiques qui vont avec.
Si on prend le découpage classique de l’espace mémoire, les adresses inférieures à 0xc0000000 (3 Go) correspondent à l’utilisateur, et le dernier Giga au noyau. On retrouve ce découpage au niveau du PGD où les premières entrées correspondent à l’espace utilisateur, et les dernières à l’espace noyau. Mais l’espace noyau est commun à tous les processus, donc tous les processus ont des entrées communes pour cette partie de la mémoire. Elles correspondent à ce qu’on appelle le master kernel PGD (son adresse est placée dans la variable swapper_pg_dir). Derrière ce nom pompeux, se cache simplement le PGD du noyau, c’est-à-dire les pages physiques utilisées par le noyau lui-même. Ainsi, selon le contexte d’exécution, on sait toujours à quel PGD se référer : swapper_pg_dir en mode noyau, celui de la tâche en mode utilisateur (même si celui de la tâche, répétons-le, contient des entrées sur les pages noyau).
Selon les architectures, certains de ces niveaux se contentent de passer la main au niveau suivant. Ainsi, sur x86_64, on a l’organisation suivante :

 // asm-x86_64/pgtable.h
/*
 * PGDIR_SHIFT determines what a top-level page table
 * entry can map
 */
#define PGDIR_SHIFT     39
#define PTRS_PER_PGD    512
/*
 * 3rd level page
 */
#define PUD_SHIFT       30
#define PTRS_PER_PUD    512
/*
 * PMD_SHIFT determines the size of the area a middle-level
 * page table can map
 */
#define PMD_SHIFT       21
#define PTRS_PER_PMD    512
/*
 * entries per page directory level
 */
#define PTRS_PER_PTE    512
#define pgd_index(address)
     (((address) >> PGDIR_SHIFT) & (PTRS_PER_PGD-1))
#define pud_index(address)
     (((address) >> PUD_SHIFT) & (PTRS_PER_PUD-1))
#define pmd_index(address)
     (((address) >> PMD_SHIFT) & (PTRS_PER_PMD-1))

En revanche, sur i386 en mode standard, la pagination se fait sur 2 niveaux uniquement (contre 3 pour le mode PAE). Nous ne détaillerons pas plus le fonctionnement et l’organisation des structures liées à la pagination, alors entrons (enfin) dans le vif du sujet.

Petit voyage au centre du noyau ou notre module vu de dehors

Dans la suite, nous donnerons du code simplifié, sans la gestion des erreurs ou quelques autres aspects "secondaires". Nous nous appuierons sur l’exemple suivant :

$ sudo insmode ./kpage.ko
$ cat /proc/`pidof top`/maps
00400000-0040d000 r-xp 00000000 09:02 130982            /usr/bin/top
0050d000-0050e000 rw-p 0000d000 09:02 130982            /usr/bin/top
0050e000-00532000 rw-p 0050e000 00:00 0                 [heap]
2b5cdea1e000-2b5cdea35000 r-xp 00000000 09:01 482137    /lib/ld-2.3.6.so
2b5cdea35000-2b5cdea38000 rw-p 2b5cdea35000 00:00 0
2b5cdeb34000-2b5cdeb36000 rw-p 00016000 09:01 482137    /lib/ld-2.3.6.so
2b5cdeb36000-2b5cdeb43000 r-xp 00000000 09:01 482065    /lib/libproc-3.2.7.so
2b5cdeb43000-2b5cdec43000 ---p 0000d000 09:01 482065    /lib/libproc-3.2.7.so
2b5cdec43000-2b5cdec44000 rw-p 0000d000 09:01 482065    /lib/libproc-3.2.7.so
...
2b5cdf529000-2b5cdf52b000 rw-p 00009000 09:01 481957    /lib/libnss_files-2.3.6.so
7fffcc076000-7fffcc08c000 rw-p 7fffcc076000 00:00 0     [stack]
ffffffffff600000-ffffffffffe00000 ---p 00000000 00:00 0 [vdso]

Le chargement du module crée une nouvelle entrée dans /proc :

$ ls /proc/kpage
cr4 efer param pgd pmd pte pud rdump xdump

cr4 et efer affichent le contenu de registres qui ne sont normalement accessibles qu’en mode privilégié. param est l’entrée que nous utilisons pour passer les paramètres à notre module (PID et adresse). pgd, pud, pmd et pte affichent les tableaux complets, ainsi que les informations relatives à l’adresse passée en argument. Enfin, rdump et xdump donnent accès aux pages mémoires directement.
On examine dans le /proc l’organisation de sa mémoire pour déterminer quelle adresse nous préoccupe. On pourrait prendre n’importe laquelle dans l’espace d’adressage, mais autant en prendre une valide. Notre choix porte sur 0x7fffcc08a000 qui ne se trouve pas trop loin du sommet de la pile, et devrait donc contenir des informations :

$ sudo echo `pidof top` 0x7fffcc08a000 > /proc/kpage/param

Nous pouvons maintenant aller lire les différentes entrées correspondant à l’adresse choisie :

 $ sudo cat /proc/kpage/pgd /proc/kpage/pud /proc/kpage/pmd /proc/kpage/pte
BASE PGD=0xffff81000ffc2000 => idx=86  current=0xffff81000ffc22b0 (pgd_k=0xffff81002ea28000)
   ffff81000ffc2000   0 000: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000065259000 NX=0
-> ffff81000ffc22b0  86 056: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x000000001138f000 NX=0
   ffff81000ffc27f8 255 0ff: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x000000005cd73000 NX=0
   ffff81000ffc2810 258 102: Present=1 R/W=W U/S=S Access=1 PhyPgSz=4k(pte) base=0x0000000000008000 NX=0
   ffff81000ffc2c20 388 184: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x00000000bd5d8000 NX=0
   ffff81000ffc2ff8 511 1ff: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000000203000 NX=0
BASE PUD=0xffff81001138f000 => idx=371 current=0xffff81001138fb98
-> ffff81001138fb98 371 173: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000066445000 NX=0
BASE PMD=0xffff810066445000 => idx=250 current=0xffff8100664457d0
   ffff8100664457a8 245 0f5: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x000000003b000000 NX=0
   ffff8100664457b0 246 0f6: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x000000001aa03000 NX=0
   ffff8100664457b8 247 0f7: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000092d18000 NX=0
   ffff8100664457c0 248 0f8: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000087420000 NX=0
   ffff8100664457c8 249 0f9: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000039ba7000 NX=0
-> ffff8100664457d0 250 0fa: Present=1 R/W=W U/S=U Access=1 PhyPgSz=4k(pte) base=0x0000000071a0f000 NX=0
BASE PTE=0xffff810071a0f000 => idx=297 (129) current=0xffff810071a0f948
   ffff810071a0f0f0  30 01e: Present=1 R/W=W U/S=U Access=1 Dirty=1 Glob=0 base=0x0000000077892000 NX=1
   ffff810071a0f0f8  31 01f: Present=1 R/W=W U/S=U Access=1 Dirty=1 Glob=0 base=0x00000000562bc000 NX=1
   ffff810071a0f100  32 020: Present=1 R/W=R U/S=U Access=1 Dirty=0 Glob=0 base=0x00000000bb84e000 NX=0
   ffff810071a0f108  33 021: Present=1 R/W=R U/S=U Access=1 Dirty=0 Glob=0 base=0x00000000bb84f000 NX=0
   ffff810071a0f110  34 022: Present=1 R/W=R U/S=U Access=1 Dirty=0 Glob=0 base=0x00000000bca6c000 NX=0
   ffff810071a0f140  40 028: Present=1 R/W=R U/S=U Access=1 Dirty=0 Glob=0 base=0x00000000bb818000 NX=0
-> ffff810071a0f948 297 129: Present=1 R/W=W U/S=U Access=1 Dirty=1 Glob=0 base=0x000000005a1d6000 NX=1
   ffff810071a0f950 298 12a: Present=1 R/W=W U/S=U Access=1 Dirty=1 Glob=0 base=0x0000000066fe6000 NX=1

Le filesystem /proc

Toute l’interaction avec notre module se fait dans le /proc. Il s’agit d’un système de fichiers virtuel. Pour cela, on crée le répertoire (fonction proc_mkdir()), puis on le peuple avec nos fichiers (fonction create_proc_entry()) :

//On crée le répertoire
kp_dir = proc_mkdir(MODULE_NAME, NULL);
kp_dir->owner = THIS_MODULE;
// On crée l’entrée param pour passer les arguments
kp_param = create_proc_entry( "param", DEFAULT_RW_PERMS, kp_dir);
kp_param->owner = THIS_MODULE;
kp_param->read_proc = kpage_read_param;
kp_param->write_proc = kpage_write_param;
// Idem pour le PGD
kp_pgd = create_proc_entry( "pgd", DEFAULT_R_PERMS, kp_dir);
kp_pgd->owner = THIS_MODULE;
kp_pgd->proc_fops = &pgd_operations;
// Et ainsi de suite ...

Pour chaque entrée, on définit les opérations associées. Dans le cas de param, on utilise directement les pointeurs sur les fonctions {read|write}_proc. En revanche, pour le PGD, on passe par une structure struct file_operations *proc_fops plus générale qui permet d’un coup de définir toutes les opérations (voir include/linux/proc_fs.h). Regardons maintenant ces différences.

La gestion des paramètres

L’entrée param nous sert à passer les arguments à notre module. Il nous faut donc lire et écrire dans cette entrée, et définir les opérations associées.
On utilise un simple echo pour passer nos arguments dans /proc/param. Derrière cela, se cache la fonction kpage_write_param() qui lit ce qui est écrit, et l’utilise pour initialiser les données internes :

int kpage_write_param( struct file *filp, const char __user *buff,
                       unsigned long len, void *data )
{
    char cmdline[CMDLINE_LENGTH];
    struct task_struct *p;
    ...
    /* passage du user space dans le kernel space */
    if (copy_from_user( &cmdline, buff, len )) {
        return -EFAULT;
    }
    cmdline[len] = ‘\0’;
    ...
    /* Plein d’opérations sur les structures internes du module pour
       sauvegarder les éléments */
    memset(&kparam, 0, sizeof(kparam));
    kparam.dlen = PAGE_SIZE;
    if ( (sscanf(cmdline, "%lu %lx %ld",
     (unsigned long*)&kparam.pid, &kparam.vaddr, &kparam.dlen) == 0)
     || (kparam.pid == 0) || (kparam.vaddr == 0) ) {
        printk(KERN_ERR "kpage: invalid parameter(s) in cmdline.\n");
        return -EINVAL;
    }
    kparam.pgd = pgd_offset(p->mm, kparam.vaddr);
    if (pgd_none(*kparam.pgd))
        return len;
    ...
    return len;
}

Quand on lit l’entrée param, on affiche les informations sur l’adresse précédemment écrite dans param (ici, on a changé par rapport à l’adresse précédente) :

$ sudo cat /proc/kpage/param
PID = 6378
vaddr = 0x00002b5cdf529000
pgd idx = 056 00002b0000000000
pud idx = 173 0000005cc0000000
pmd idx = 0fa 000000001f400000
pte idx = 129 0000000000129000
dlen = 4096

Pour cela, la fonction de lecture, kpage_read_param(), affiche simplement les informations en allant les chercher où elles sont. Cette fonction doit retourner le nombre de caractères écrits :

int kpage_read_param( char *page, char **start, off_t off,
                    int count, int *eof, void *data )
{
    len += sprintf(page+len, “PID = %lu\n”
                  “vaddr = 0x%016lx\n”
                  “pgd idx = %03lx %016lx\n”
                  “pud idx = %03lx %016lx\n”
		  ...
                  (unsigned long)kparam.pid,
                  kparam.vaddr,
                  pgd_index(kparam.vaddr),
		  ...
	 	  );
  return len;
}

Le problème de cette approche est que le buffer utilisé pour écrire/lire est de taille finie, voire insuffisante. Si on lit/écrit plus de 1024 caractères, le buffer étant circulaire, on revient au début (enfin, tout ceci n’est pas strictement vrai, mais c’est le principe). Nous ne pouvons donc pas utiliser ces opérations directes de lecture/écriture pour les entrées sur les pages, car on risque de dépasser largement les 1024 caractères. Par exemple, si on prend les entrées rdump et xdump, elles affichent des pages complètes, soit 4 Ko. Pour cela, on utilise une autre méthode, itérative, fournie par le noyau.

Lecture itérative

Nous nous concentrons sur le cas du PGD, les autres étant similaires. Cette fois, nous devons donc définir une fonction itérative associée à la lecture de l’entrée :

int pgd_show(struct seq_file *p, void *v)
{
    int i =  *(loff_t *) v;
    ...
    seq_printf(p, "%s %p ",
      i == pgd_index(kparam.vaddr) ? "->" : "  ",
      &t->mm->pgd[i]);
    ...
    return 0;
}

Ce bref code se concentre sur l’affichage. Tout d’abord, les arguments de la fonction sont tout d’abord un fichier dans lequel on écrit, puis un pointeur sur void. Le fichier n’est pas un fichier classique, mais un fichier séquentiel qui permet des opérations "par bloc" (include/linux/seq_file.h). En fait, il s’agit d’un fichier muni d’un itérateur :

// include/linux/seq_file.h
struct seq_operations {
  void * (*start) (struct seq_file *m, loff_t *pos);
  void (*stop) (struct seq_file *m, void *v);
  void * (*next) (struct seq_file *m, void *v, loff_t *pos);
  int (*show) (struct seq_file *m, void *v);
};

En définissant ces opérations, on bénéficie d’une lecture séquentielle du fichier. Or, jusqu’à présent, nous avons uniquement défini la fonction show(). Les autres sont celles qui gèrent l’itérateur :

• start() sert à renvoyer l’index à traiter ou NULL si on est au-delà de ce qu’on souhaite traiter ;
• next() gère l’incrémentation du compteur ;
• stop(), on s’en moque, car on gère ça avant.

Comme on va faire exactement les mêmes choses pour les PGD, PUD, PMD et PTE, et qu’en plus on est flemmard, on va utiliser des macros pour tout faire d’un coup :

 #define PGTABLE_SEQ_ITER(pgtable, limit) \
    static void * pgtable##_seq_start(struct seq_file *f, loff_t *pos) \
    {                                                                  \
        return (*pos < limit ) ? pos : NULL;                           \
    }                                                                  \
    static void * pgtable##_seq_next(struct seq_file *f, void *v, loff_t *pos) \
    {                                                                  \
        (*pos)++;                                                      \
        if (*pos >= limit)                                             \
                return NULL;                                           \
        return pos;                                                    \
    }                                                                  \
    static void pgtable##_seq_stop(struct seq_file *f, void *v)        \
    {                                                                  \
        /* Nothing to do */                                            \
    }                                                                  \
                                                                       \
    static struct seq_operations pgtable##_seq_ops = {                 \
        .start = pgtable##_seq_start,                                  \
        .next  = pgtable##_seq_next,                                   \
        .stop  = pgtable##_seq_stop,                                   \
        .show  = pgtable##_show                                        \
   };                                                                  \
    static int pgtable##_open(struct inode *inode, struct file *filp)  \
    {                                                                  \
        return seq_open(filp, & pgtable##_seq_ops);                    \
    }                                                                  \
      struct file_operations pgtable##_operations = {                  \
        .open           = pgtable##_open,                              \
        .read           = seq_read,                                    \
        .llseek         = seq_lseek,                                   \
        .release        = seq_release,                                 \
    };
PGTABLE_SEQ_ITER(pgd, PTRS_PER_PGD)
PGTABLE_SEQ_ITER(pud, PTRS_PER_PUD)
PGTABLE_SEQ_ITER(pmd, PTRS_PER_PMD)
PGTABLE_SEQ_ITER(pte, PTRS_PER_PTE)

Grâce au ##, qui sert à la concaténation, on définit très vite toutes nos fonctions, et on remplit les structures pour chaque type de tableau de pages. Et voilà, on sait maintenant lire/écrire des entrées, soit par la méthode classique, soit en mode itératif.

Petit voyage au centre du noyau ou notre module vu de dedans

Puisque nous voulons parcourir les différents répertoires de pages, commençons par le commencement, le PGD. En fait, chaque tâche possède son propre PGD, c’est ce qui permet de distinguer quelles pages appartiennent à qui. À chaque changement de tâche, le registre CR3 est mis à jour, avec l’adresse du PGD correspondant à la tâche qui va s’exécuter.
Or, comme nous sommes dans le noyau à exécuter le code de notre module, CR3 contient l’adresse du PGD... du noyau, et non de la tâche souhaitée. En fait, ce PGD est sauvegardé dans le descripteur des tâches, task_struct (include/linux/sched.h). Ce descripteur contient un pointeur sur une structure qui décrit complètement la mémoire de la tâche (mm_struct, toujours dans sched.h), qui à son tour contient l’adresse du PGD de la tâche.
Comment y accéder : il faut d’abord récupérer le descripteur de tâche, puis accéder aux différents éléments au travers des structures impliquées :

int pgd_show(struct seq_file *p, void *v)
{
    int i =  *(loff_t *) v;
    struct task_struct *t = find_task_by_pid(kparam.pid);
    __asm__ __volatile__("mov %%cr3, %0"
                         : “=r”(cr3)
        );
    /* Affiche les info relatives a notre
       adresse sur la premiere ligne */
    if (0 == i) {
      seq_printf(p, "BASE PGD=0x%p => idx=%-3ld "
                    "current=0x%p (pgd_k=0x%lx) \n",
       t->mm->pgd, pgd_index(kparam.vaddr),
       kparam.pgd, cr3+PAGE_OFFSET
      );
    }
   /* Affiche chaque ligne de la PGD */
    if ( !pgd_none(t->mm->pgd[i]) ) {
        seq_printf(p, "%s %p ",
                i == pgd_index(kparam.vaddr) ? "->" : "  ",
                &t->mm->pgd[i]);
        dump_pte(p, i, pgd_val(t->mm->pgd[i]), 0);
    }
    return 0;
}

Quelques remarques sur le code qui précède :

• On met de l’assembleur inline pour récupérer le registre CR3 qui contient le PGD du noyau.
• On utilise la lecture itérative pour faire un affichage spécial si 0==i. Remarquez l’écriture, avec le 0 à gauche : c’est une habitude à prendre qui permet d’éviter les malencontreux oublis d’un signe =. En effet, si vous écrivez i=0 dans une condition, le compilateur ne se plaindra pas et votre programme risque d’avoir un comportement non désiré. En revanche, 0=i provoque une erreur du compilateur.
• Enfin, s’il y a une entrée dans le PGD (pgd_none()), on affiche les informations relatives en appelant la fonction générique dump_pte().
• La macro pgd_index() convertit les bits de l’adresse virtuelle en l’index dans la PGD (on trouve les mêmes fonctions pour les autres niveaux).

Revenons quelques instants sur la pagination. Pour se promener dans les répertoires, on doit à chaque niveau, accéder à l’entrée du répertoire courant, qui pointe sur la table suivante. Regardons comment cela fonctionne au niveau du PUD :

 // kparam.vaddr contient l’adresse virtuelle
 // on récupère l’index à partir de l’adresse
 idx = pud_index(kparam.vaddr);
 // On récupère la base du PUD à partir du PGD et de l’adresse
 kparam.pud = pud_offset(kparam.pgd, kparam.vaddr);
 // on remonte du PUD courant à la base
 pud = kparam.pud - idx;

En fait, pud_offset() nous donne directement le bon PUD. Pour passer du PGD à la base du PUD suivant, on devrait faire (écriture symbolique) :

pgd = cr3
pud = pgd[ pgd_index(vaddr) ]
pmd = pud[ pud_index(vaddr) ]
pte = pmd[ pmd_index(vaddr) ]

Et quand on met tout ça ensemble : rdump et xdump

Ces 2 entrées sont destinées à dumper les pages mémoires des processus. xdump affiche conjointement le code hexa et sa transcription en ascii de chaque octet. rdump fait un affichage raw, ce qui est très pratique pour combiner avec d’autres programmes (par exemple, pour désassembler un programme protéger, en "pipant"dans ndisasm).

$ echo `pidof top` 0x7fffcc08a000 > /proc/kpage/param
$ cat /proc/kpage/xdump
Dumping vaddr=0x00007fffcc08a000 paddr=0x00000000baf6b000
...
00007fffcc08ae90: 00 50 41 54 48 3d 2f 75  73 72 2f 6c 6f 63 61 6c  .PATH=/usr/local
00007fffcc08aea0: 2f 73 62 69 6e 3a 2f 75  73 72 2f 6c 6f 63 61 6c  /sbin:/usr/local
00007fffcc08aeb0: 2f 62 69 6e 3a 2f 75 73  72 2f 73 62 69 6e 3a 2f  /bin:/usr/sbin:/
00007fffcc08aec0: 75 73 72 2f 62 69 6e 3a  2f 73 62 69 6e 3a 2f 62  usr/bin:/sbin:/b
00007fffcc08aed0: 69 6e 3a 2f 75 73 72 2f  58 31 31 52 36 2f 62 69  in:/usr/X11R6/bi
00007fffcc08aee0: 6e 00 53 54 59 3d 36 33  36 30 2e 73 68 00 50 57  n.STY=6360.sh.PW
00007fffcc08aef0: 44 3d 2f 68 6f 6d 65 2f  72 61 79 6e 61 6c 2f 4d  D=/home/raynal/M
00007fffcc08af00: 49 53 43 2f 6b 70 61 67  65 2f 6b 70 61 67 65 00  ISC/kpage/kpage.
00007fffcc08af10: 4c 41 4e 47 3d 65 6e 5f  55 53 2e 49 53 4f 2d 38  LANG=en_US.ISO-8
00007fffcc08af20: 38 35 39 2d 31 35 00 48  4f 4d 45 3d 2f 68 6f 6d  859-15.HOME=/hom
00007fffcc08af30: 65 2f 72 61 79 6e 61 6c  00 53 55 44 4f 5f 43 4f  e/raynal.SUDO_CO
00007fffcc08af40: 4d 4d 41 4e 44 3d 2f 62  69 6e 2f 62 61 73 68 00  MMAND=/bin/bash.
00007fffcc08af50: 53 48 4c 56 4c 3d 32 00  4c 41 4e 47 55 41 47 45  SHLVL=2.LANGUAGE
...

On passe par une lecture itérative étant donnée la quantité d’octets à retranscrire. On commence par donner l’adresse physique correspondant à l’adresse virtuelle passée en argument. Ensuite, on navigue au sein des répertoires de page pour atteindre la vraie page physique, et afficher son contenu :

char *ptr;
pte = lookup_vaddr(kparam.pgd, vaddr);
ptr = (char*)( (pte_val(*pte)&PTE_MASK)) +
   PAGE_OFFSET + (kparam.vaddr&~PAGE_MASK);

Comment accéder réellement aux octets de la page physique ? En fait, on peut y accéder au travers de la mémoire du noyau qui contient un mapping direct pour cela. On récupère donc l’adresse physique à partir du PTE, via l’opération pte_val(*kparam.pte)&PTE_MASK. Mais on ne peut pas utiliser directement cette adresse physique pour atteindre la page puisque le noyau ne sait utiliser que des adresses virtuelles. On doit donc "reconvertir" cette adresse en une adresse virtuelle. Mais pas n’importe laquelle ! On va utiliser une fonctionnalité du noyau, qui contient son propre mapping de TOUTES les pages physiques. En effet, pour accéder à une adresse physique depuis le noyau, il suffit d’y ajouter PAGE_OFFSET. Ensuite, on extrait l’offset de l’adresse qu’on veut, comme on le fait pour les index des tables de répertoire (l’offset correspond aux derniers bits de l’adresse virtuelle). Ainsi, ptr est une adresse virtuelle qui pointe sur la bonne page physique.
Un des intérêts de ce mécanisme est que si plusieurs processus sont des instances du même programme (un shell par exemple), certaines pages ne sont chargées qu’une fois en mémoire. Les adresses virtuelles seront très probablement différentes. Mais les pages physiques correspondantes seront les mêmes tant qu’elles n’auront pas été modifiées.

Last words...

Le mode noyau donne une compréhension très précise de ce qui se passe. Programmer en mode noyau n’est pas simple, d’autant qu’il y a énormément de contraintes auxquelles nous ne sommes pas habitués : passage des arguments entre espace utilisateur et espace noyau, gestion des conditions de concurrence, allocateurs mémoires, dead locks, etc. Il s’agit réellement d’un autre monde. C’est ce qui fait que c’est sans doute à la fois si compliqué de s’y aventurer, mais aussi tellement intéressant !!!
Nous avons vu comment un petit module a priori tout simple pouvait mettre en jeu de nombreux mécanismes qu’on utilise parfois sans s’en rendre compte (le /proc, la conversion d’adresse via la pagination). Faire ses propres programmes de test n’est pas si compliqué. On risque juste de cramer sa machine ;-) Utilisez toujours une machine virtuelle pour faire vos tests, c’est beaucoup plus sûr. En effet, si vous vous ratez en mode noyau, ce n’est pas un processus qui plante, c’est le noyau, avec des effets imprévisibles potentiellement destructeurs...
[1] kpage, à télécharger sur http://miscmag.com/files/28/kpage/

Linux : stabilité et pilotes, peut-on améliorer les choses ?

Notre noyau favori est remarquable en plusieurs points ; apprécié pour sa robustesse et sa fiabilité, il tourne sur une variété de plateformes impressionnante, gère une base de matériel record et est développé par un très grand nombre de contributeurs. Ce qui fait sa force représente aussi une de ses faiblesses : le code afférant à la gestion des périphériques représente environ 70% du volume de code total de Linux, et, selon une étude de l’université de Stanford, Californie, il serait à l’origine des 3 à 7 fois plus de plantages entraînant un crash de l’ensemble du noyau que les autres portions du code (mesures automatiques effectuées sur des noyaux 2.0 à 2.4). D’autres mesures effectuées cette fois sur Windows XP concluent que 85% des plantages sont dus aux pilotes.

Une question d’architecture

Mais pourquoi Linux est-il si sensible à l’influence de pilotes ? Qu’en est-il ailleurs ? C’est principalement une question de design. On peut ainsi distinguer plusieurs catégories de noyaux existants, dont voici les principales :

• Les micro-noyaux : dans ce cas, un cœur minimaliste assure les fonctions de base (gestion de la mémoire, des tâches, accès basique au matériel...). Ce sont d’autres modules qui assurent le reste (pilotes, systèmes de fichiers, réseau...), en espace utilisateur. Mach ou encore L4 (HURD) en sont des exemples. HURD en particulier est conçu pour que l’on puisse altérer, ajouter et retirer ces modules sans affecter du tout le reste du système ; ils communiquent entre eux au moyen d’interfaces RPC (Remote Procedure Call), et sont chacun isolés dans leur zone mémoire, sans pouvoir en déborder. Le principal inconvénient de cette approche est le coût des communications entre les différentes parties du système, et entre les espaces noyau et utilisateur. En effet, si chaque composant du système forme une entité indépendante, chaque appel à l’un d’entre eux, chaque communication entre modules requiert des context switches (changement de contexte) : sauvegarde des registres processeur concernant la tâche en cours, chargement dans les registres des informations de la tâche suivante, et ainsi de suite ; ce type d’opération est coûteux en cycles CPU, spécialement sur architectures x86.
• Les noyaux monolithiques : le noyau est un ensemble regroupant toutes les fonctions telles que gestion des processus, gestion mémoire, pilotes de périphériques, systèmes de fichiers... Les différentes parties du système ne sont pas isolables et sont fortement couplées les unes aux autres. Linux et les BSD sont des noyaux monolithiques. Ces systèmes offrent de bonnes performances, mais chaque partie peut en théorie affecter le reste du système, étant donné qu’il n’y a pas de protections (mémoire, routines et structures internes).

• Les noyaux hybrides : ce sont à la base des micro-noyaux, mais pour offrir un bon compromis de performances, le cœur du noyau se charge de tâches normalement dévolues aux services en espace utilisateur dans les micro-noyaux purs (accès au matériel...). C’est le choix retenu par les noyaux NT (Microsoft) et XNU (OSX).

Linux, ainsi que d’autres systèmes, ne sont en fait plus strictement monolithiques, mais monolithiques modulaires. Ainsi, sous notre OS, il est possible depuis longtemps de rajouter et retirer des objets noyau (tout code de type kernel object), que nous appelons couramment modules (pensez aux célèbres insmod/modprobe/rmmod), ou encore de modifier les gestionnaires d’entrées/sorties et de tâches en cours d’exécution. Cependant, ces fonctionnalités ont été intégrées dans un but de gain de place et de souplesse, en ne chargeant que du code utile à un système donné. Cette organisation est défendue par Linus Torvalds, qui s’est opposé depuis longtemps au principe de micro-noyau. Cependant les réflexions vont bon train depuis de nombreuses années pour trouver des solutions alliant la performance d’une approche monolithique et la robustesse d’une approche entièrement modulaire. En fait, dans la partie qui nous intéresse, à savoir améliorer l’indépendance entre le cœur et les pilotes, plusieurs pistes sont explorées par différents projets, chacune ayant ses avantages, mais aucune n’étant parfaite, ni sur le point d’être adoptée.

Pilotes en espace utilisateur

Plusieurs projets ont tenté d’offrir la possibilité de déplacer les pilotes, ou du moins une partie d’entre eux, en espace utilisateur. Il existe déjà de tels pilotes de périphériques (pilotes Xorg, certains drivers USB ou parallèle...), mais qui n’ont pas accès à des fonctions de bas niveau, assurées par le noyau ; c’est pourquoi on ne trouve pas de pilotes en espace utilisateur pour les périphériques connectés sur bus de type PCI. Ainsi, s’il est possible d’accéder aux pages mémoires des périphériques via /dev/(k)mem, et de connaître les IRQ et ports d’entrées/sorties qu’ils utilisent, il n’y a aucun moyen de s’enregistrer comme "destinataire" d’une interruption, ni d’être notifié de leur arrivée. Principalement, on peut dire que les derniers remparts à un support du matériel sans intervention du noyau sont la gestion des interruptions (IRQ) et l’accès aux zones DMA. Plusieurs tentatives de solutions ont été proposées pour inclusion dans le noyau. Parmi elles, celle de Peter Chubb en 2004, et, à la dernière rentrée, celle de Thomas Gleixner soutenue par Greg Kroah-Hartman (développeur noyau Suse). Il propose l’ajout d’une nouvelle structure, iio_device(), chargée d’enregistrer un nouveau périphérique et de fournir des informations sur ce dernier, ainsi que des fonctions exportées en espace utilisateur (iio_read, iio_write()...). À charge des développeurs du pilote de créer un module noyau léger, chargé de la gestion des interruptions et de la faire communiquer avec l’userspace. Ce choix part du principe que ce travail peut être très spécifique à un périphérique.
La question des pilotes en userspace a déclenché une discussion acharnée sur la LKML. D’un côté, les pilotes développés séparément du noyau seraient plus faciles à écrire, et moins enclins à déstabiliser l’ensemble du système en cas de plantage : étant considérés comme des programmes classiques, ils ne peuvent atteindre les structures du noyau ni son espace mémoire, et peuvent être lancés ou détruits aisément. De l’autre côté, proposer une interface d’accès stable communiquant avec un programme en espace utilisateur ne manquerait certainement pas d’intéresser les vendeurs de matériels, qui pourraient y voir un moyen de développer des pilotes sous Linux sans être soumis à la "contrainte" de les placer sous GPL (rappelons que tout travail directement interfacé au noyau doit se soumettre à la GPL, tandis que l’espace utilisateur n’est pas concerné), ni de suivre les fréquents changements internes des interfaces noyau, ou encore de développer leur propre module intermédiaire en GPL s’interfaçant avec leur BLOB. Par exemple, Linus s’est fermement prononcé contre ce type de projets, à moins qu’on lui démontre que leur utilité dépasse les inconvénients ; il ne souhaite pas ouvrir une porte supplémentaire aux pilotes binaires propriétaires, ni transformer peu à peu Linux en système à micro-noyau.
Signalons, à titre anecdotique, une approche différente, mais touchant également au domaine des privilèges d’exécution : David Kaplan, étudiant à l’université de l’Illinois (USA), a imaginé et implémenté RingCycle, une solution où les pilotes s’exécutent sur les niveaux de privilèges intermédiaires des processeurs de type x86. Cette architecture définit 4 niveaux de privilèges (ou anneaux, rings), un code s’exécutant sur le niveau n n’ayant le droit d’intervenir que dans les niveaux égaux ou inférieurs. Linux n’utilise que deux anneaux : 0 pour le noyau et 3 pour l’espace utilisateur. RingCycle propose donc de faire tourner les pilotes dans des threads en ring 1, et de faire passer les appels noyau via une API intermédiaire (appelée "Driver API") au moyen d’appels x86 lcall et lret. Cette solution nécessite très peu de modifications au code actuel des drivers, mais est réservée à une seule architecture processeur.
La page du projet : http://www.acm.uiuc.edu/projects/RingCycle.

SafeDrive et Shadow drivers

Une deuxième piste consiste à tenter d’isoler certaines opérations des pilotes par une couche légère chargée d’intercepter, de vérifier les appels système, voire de décharger-relancer un pilote ayant crashé. Les deux technologies présentées ici ont pour but la fiabilité de fonctionnement en cas d’erreur accidentelle, et ne concernent pas la sécurité ou les codes malveillants.
Les membres du projet SafeDrive de l’université de Berkeley sont partis du constat que ce sont très souvent les requêtes demandées par le système au pilote ou une réception de données inattendue par le pilote qui génèrent des plantages. Le projet a pour but de vérifier la pertinence des données qui sont échangées entre le noyau et un pilote ou encore directement dans un pilote. SafeDrive permet, par exemple, de savoir si l’assignement de variable se fait correctement dans son type et dans sa capacité, par vérification de type des pointeurs et des débordements de tableaux. En pratique, ceci est assuré par la première partie du projet : avant compilation d’un pilote, un outil appelé "Deputy" utilise les informations insérées par les développeurs dans les fichiers d’en-tête (headers) ou dans le code pour ajouter au fichier source des lignes de code supplémentaires telles que des appels à assert (macro qui renvoie faux si la condition passée en argument n’est pas remplie). On obtient ainsi une vérification à l’exécution, réservée d’ordinaire plutôt aux langages de haut niveau. Par exemple, le code suivant, tiré de la documentation officielle de Safedrive (en rouge, l’annotation du développeur à l’attention de Deputy) :

struct e1000_tx_ring {
  [...]
  unsigned int info_count;
  struct e1000_buffer * count(info_count)
      buffer_info;
  [...]
};

static boolean_t
e1000_clean_tx_irq(
    struct e1000_adapter *adapter,
    struct e1000_tx_ring *tx_ring)
{
  [...]
  i = tx_ring->next_to_clean;
  eop = tx_ring->buffer_info[i]
                   .next_to_watch;
}

deviendrait, après moulinage par Deputy :

struct e1000_tx_ring {
  [...]
  unsigned int info_count;
  struct e1000_buffer *buffer_info;
  [...]
};

static boolean_t
e1000_clean_tx_irq(
    struct e1000_adapter *adapter,
    struct e1000_tx_ring *tx_ring)
{
  [...]
  i = tx_ring->next_to_clean;
  <b>assert(0 <= i && i < tx_ring->info_count);</b>
  eop = tx_ring->buffer_info[i]
                   .next_to_watch;
}

La seconde partie est une couche intermédiaire légère entre le noyau et les pilotes. Elle est chargée de mémoriser les dernières actions faites sur le noyau devant être annulées si un pilote plante, et reçoit les appels émis par le code Deputy en cas de problème. Le cas échéant, le module fautif est déchargé, l’état du noyau restauré, et le module peut être rechargé automatiquement afin que le système retrouve un état de fonctionnement complet. Le bon fonctionnement de SafeDrive repose donc sur une préparation du code par ses développeurs. Pour approfondir le sujet, je vous invite à consulter http://ivy.cs.berkeley.edu/safedrive/.
Valerie Hansen, développeuse chez Intel, a récemment relancé sur lwn.net le concept de shadow drivers développé, quant à lui, par l’université de Washington. Cette technique se décompose, à l’instar de SafeDrive, en deux parties. Côté pilotes, chaque catégorie d’entre eux (IDE, réseau...) dispose d’un pseudo-pilote qui est "branché" en parallèle à un "vrai" pilote et est appelé shadow driver (pilote fantôme). Tant que tout se passe correctement, il est en mode dit "passif" et espionne les appels système (ioctl()) en les mémorisant. Si le pilote auquel il est couplé plante, il passe en mode dit "actif", et joue un rôle de proxy : il accepte et répond aux requêtes du noyau comme si de rien n’était. Pendant ce temps-là, le pilote fautif est déchargé, puis rechargé. Les structures noyau allouées par les pilotes sont maintenues, ce qui évite au noyau de remarquer que le pilote n’est plus présent. Les appels faits précédemment au noyau, qui étaient logués en mode passif, sont annulés, afin que celui revienne dans un état cohérent ; notre shadow driver rejoue alors les appels enregistrés au pilote fraîchement rechargé, afin de le remettre dans le même état qu’avant le plantage. Ce dernier recommence alors à traiter les requêtes et à y répondre. Fin de l’incident : le shadow driver retourne en mode passif. Pendant ce temps, aucun message d’erreur n’a donc été transmis aux applications, qui continuent à fonctionner comme si de rien n’était. Ces pilotes fantômes s’appuient sur l’infrastructure Nooks. Nooks est une couche isolant les appels système depuis ou vers les pilotes, et qui détecte les erreurs comme les fautes de protection mémoire, le passage de mauvais paramètres, ou encore un usage CPU trop intensif. Concrètement, chaque driver s’exécute dans un sous-système appelé "nook", qui se charge d’intercepter les appels entre noyau et pilote, émule les appels aux registres du périphérique et transfère les interruptions. Chaque nook tourne en espace noyau, mais est un domaine protégé interdisant les débordements mémoires.
L’approche de Nooks + shadow drivers requiert des modifications de code légères pour porter les pilotes existants sur cette infrastructure. À noter que Nooks a été développé sur un noyau 2.4.18, et ne fonctionne en l’état que sur des systèmes monoprocesseurs. La page officielle du projet est http://nooks.cs.washington.edu/
Quelle que soit la solution retenue, l’adoption d’une technique permettant de protéger le cœur du noyau des pilotes aura un coût en ressources système, car elle impliquera, quelle qu’en soit l’implémentation, des vérifications supplémentaires et/ou un code intermédiaire. Cependant, les recherches résumées ici se veulent rassurantes en annonçant un surcoût minime. Pour finir, un gros critère requis du point de vue des développeurs noyau est que ce genre de techniques n’implique pas d’inclure dans le noyau un code qui formerait une API stable pour la programmation de drivers, chose que beaucoup, dont Linus Torvalds, ne veulent sous aucun prétexte.