Semaine Athens Linux Device Drivers


Introduction

Le développement d'un pilote dans le noyau pose les mêmes problèmes que le développement d'une applications avec plusieurs threads. Plusieurs fonctions de votre pilote peuvent être appelées en même temps et ce, pour plusieurs raisons.

Tout d'abord, quand une fonction de votre pilote s'exécute, une interruption en provenance de votre périphérique peut interrompre la fonction pour aller exécuter le gestionnaire d'interruption de votre pilote.

Ensuite, sur un système multiprocesseur, deux fonctions de votre pilote (voir même la même fonction) peuvent s'exécuter en même temps chacune sur un processeur différent.

Il est donc important que l'accès aux ressources qui pourraient être partagées entre plusieurs fonctions de votre pilote soient contrôlé. Ces ressources peuvent être des structures de données dont il est nécessaire de garantir l'atomicité des lectures et des modifications (une tâche ne doit pas voir la structure à moitié modifiée). Cela peut également concerner le périphérique lui-même. Par exemple si une opération nécessite plusieurs échanges ininterrompus avec le périphérique, il ne faut pas qu'une autre partie de votre pilote fasse d'autres échanges pendant ce temps là.

Le noyau offre plusieurs primitives permettant de gérer l'accès concurrent à des ressources.

Variables atomiques

Sur certaines architectures, la simple incrémentation d'un entier n'est pas une opération atomique (un autre processeur essayant de lire la valeur de cet entier pendant l'opération peut récupérer une valeur autre que l'ancienne ou la nouvelle).

Le noyau fournit le type atomic_t défini dans <linux/types.h> qui contient un entier signé (dont au minimum 24 bits sont utilisables).

Les fonctions suivantes, définies dans <asm/atomic.h> permettent de manipuler ce type atomic_t :

/* Lecture / écriture */
void atomic_set(atomic_t *v, int v);
int atomic_read(atomic_t *v);

/* Opérations arithmétiques */
void atomic_inc(atomic_t *v);
void atomic_dec(atomic_t *v);
void atomic_add(int i, atomic_t *v);
void atomic_sub(int i, atomic_t *v);

int atomic_inc_return(atomic_t *v);
int atomic_dec_return(atomic_t *v);
int atomic_add_return(int i, atomic_t *v);
int atomic_sub_return(int i, atomic_t *v);

/* Renvoient une valeur != 0 si le résultat de l'opération est nul */
int atomic_inc_and_test(atomic_t *v);
int atomic_dec_and_test(atomic_t *v);
int atomic_sub_and_test(int i, atomic_t *v);

Le noyau fournit également des primitives de manipulation de bits (dans <linux/bitops.h>). Ces opérations sont également atomiques :

void set_bit(int nr, volatile unsigned long *addr);
void clear_bit(int nr, volatile unsigned long *addr);
void change_bit(int nr, volatile unsigned long *addr);

/* Modifient le bit et renvoient son _ancienne_ valeur */
int test_and_set_bit(int nr, volatile unsigned long *addr);
int test_and_clear_bit(int nr, volatile unsigned long *addr);
int test_and_change_bit(int nr, volatile unsigned long *addr);

int test_bit(int nr, const volatile unsigned long *addr);

Plus d'informations sur ces opérations atomiques sont disponibles dans Documentation/core-api/atomic_ops.rst.

Mutex

Un mutex est une primitive de synchronisation permettant de gérer l'accès à une ressource partagée (par exemple une instance d'une structure de données).

Un mutex ne peut être que dans deux états : disponible ou pris (verrouillé). Il ne peut être pris que par un seul flot d'exécution à un instant donné.

Initialisation

Les mutexes sont définis dans include/linux/mutex.h. Ils sont représentés par une structure struct mutex.

Cette structure peut être déclarée et initialisée statiquement en même temps grâce à la macro :

DEFINE_MUTEX(name);

ou initialisée dynamiquement grâce à la fonction :

void mutex_init(struct mutex *lock);

Opérations

void mutex_lock(struct mutex *lock);
int mutex_lock_killable(struct mutex *lock);
int mutex_lock_interruptible(struct mutex *lock);

Ces trois fonctions permettent de prendre (verrouiller) un mutex. Si le mutex est disponible, il est pris et ces fonctions retournent immédiatement. Si le mutex est déjà pris, elles bloquent (la tâche courante est mise en sommeil) jusqu'à ce que le mutex soit de nouveau disponible puis le prennent et rendent la main.

Pour la première fonction, l'attente ne peut pas être interrompue (avant que le mutex soit libre) et donc la tâche ne peut être tuée. Pour la seconde, l'attente peut être interrompue par un signal SIGKILL et pour la dernière, l'attente peut être interrompue par n'importe quel signal. Pour ces deux derniers cas, si l'attente est interrompue par un signal, la fonction renvoie -EINTR et le mutex n'est pas pris.

int mutex_trylock(struct mutex *lock);

Cette fonction essaie de prendre le mutex. S'il est disponible, elle le prend et retourne 1. S'il n'est pas disponible, elle renvoie 0 immédiatement sans bloquer (et sans le prendre).

void mutex_unlock(struct mutex *lock);

Cette fonction permet de rendre le mutex. Il redevient alors disponible. Si un autre flot d'exécution était bloqué en attente du mutex, il sera réveillé.

Utilisation

Remarque importante : les opérations impliquant les mutex pouvant bloquer, elles ne sont pas utilisables dans le contexte d'interruption (gestionnaire d'interruption et tasklet) !

Petit exemple simple (et inutile...) :

struct foo_struct {
   int i;
   int j;
   struct mutex lock;
};

void inc_foo(struct foo_struct *fs) {
   mutex_lock(&fs->lock);
   /* Début de la zone critique */
   fs->i++;
   fs->j++;
   /* Fin de la zone critique */
   mutex_unlock(&fs->lock);
}

void dec_foo(struct foo_struct *fs) {
   mutex_lock(&fs->lock);
   /* Début de la zone critique */
   fs->i--;
   fs->j--;
   /* Fin de la zone critique */
   mutex_unlock(&fs->lock);
}

void init_foo(struct foo_struct *fs) {
   fs->i = 0;
   fs->j = 0;
   mutex_init(&fs->lock);
}

Spinlock

L'objectif d'un spinlock est le même que celui d'un mutex. Il peut être dans deux état : libre et pris (verrouillé). Quand un flot d'exécution essaie de prendre (verrouiller) un spinlock qui l'est déjà, l'attente est active, c'est-à-dire que le processeur ne fait qu'essayer de prendre le spinlock jusqu'à ce qu'il soit de nouveau disponible. Le flot d'exécution n'est pas mis en sommeil.

Les spinlocks sont donc utilisables dans des contextes où la tâche courante n'a pas le droit de bloquer et notamment dans le contexte d'un gestionnaire d'interruption.

Une tâche ayant verrouillé un spinlock n'a pas le droit de bloquer ni d'être mis en sommeil pendant qu'elle le détient. Le spinlock doit être verrouillé le moins longtemps possible (quelques lignes de code).

Les fonctions liées à la gestion des spinlocks sont déclarées dans include/linux/spinlock.h.

Initialisation

Un spinlock peut être déclaré et initialisé statiquement grâce à la macro :

DEFINE_SPINLOCK(name)

Il peut également être initialisé dynamiquement grâce à la fonction spin_lock_init :

spinlock_t spin;
spin_lock_init(&spin);

Opérations

void spin_lock(spinlock_t *lock);
void spin_unlock(spinlock_t *lock);

La première fonction verrouille le spinlock (soit il est libre et il est verrouillé tout de suite, soit il n'est pas libre et la fonction va attendre activement jusqu'à ce qu'il le soit) mais sans désactiver les interruptions. La seconde fonction rend un spinlock préalablement verrouillé.

La fonction spin_lock peut donc être utilisée pour protéger une section de code critique uniquement dans le contexte d'un processus (i.e. entre deux fonctions autre que des gestionnaires d'interruptions dans votre pilote). En effet, si une fonction a verrouillé un spinlock à l'aide de cette méthode, est interrompue par une interruption et que le gestionnaire d'interruption essaie lui aussi de verrouiller le spinlock, le gestionnaire d'interruption ne va jamais pouvoir y arriver et va rester bloqué en attente active.

void spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags);

La première fonction verrouille le spinlock et désactive les interruptions sur le processeur courant. La deuxième rend le spinlock et réactive les interruptions (si elles l'étaient lors de l'appel à spin_lock_irqsave).

La fonction spin_lock_irqsave peut donc être utilisée pour protéger une section de code critique quel que soit le contexte. Pour reprendre l'exemple précédent, une fonction qui a verrouillé un spinlock à l'aide de cette méthode n'a pas à craindre d'être interrompue par une interruption puisque celles-ci sont désactivées sur le processeur courant. Elle est donc certaine de pouvoir arriver jusqu'au point de déverrouillage de façon atomique. Un gestionnaire d'interruption peut s'exécuter sur un autre processeur et s'il a besoin du spinlock il attendra jusqu'à sa libération qui arrivera forcément.

C'est la méthode la plus coûteuse mais qui couvre tous les cas possibles.

flags est un unsigned long dans lequel sera sauvegardé l'état des interruptions lors de l'appel à spin_lock_irqsave pour être restauré dans la fonction spin_unlock_irqrestore1.

void spin_lock_bh(spinlock_t *lock);
void spin_unlock_bh(spinlock_t *lock);

La première fonction verrouille le spinlock et désactive les softirq sur le processeur courant. La deuxième rend le spinlock et réactive les interruptions logicielles.

La fonction spin_lock_bh peut donc être utilisée pour protéger une section de code entre un contexte processus et une softirq (ou une tasklet), mais pas un véritable gestionnaire d'interruption.

int spin_trylock(spinlock_t *lock);
int spin_trylock_irqsave(spinlock_t *lock, unsigned long flags);
int spin_trylock_bh(spinlock_t *lock);

Ces fonctions verrouillent le spinlock s'il est disponible et retourne une valeur différente de 0 dans ce cas. S'il est déjà verrouillé, elles rendent la main tout de suite en renvoyant la valeur 0.

Reader/writer spinlock

Une version lecteur/écrivain (reader/writer) des spinlocks est disponible. Il peut y avoir autant de lecteurs (reader) que souhaité mais par contre l'écrivain (writer) doit avoir l'accès exclusif (aucun autre lecteur ni écrivain pendant ce temps).

L'API est la suivante :

DEFINE_RWLOCK(lock);
/* ou */
rwlock_t lock;
rwlock_init(&lock);

/* Version lecteurs : tant qu'il n'y a que des lecteurs, ne bloquent
pas, bloquent seulement si un écrivain a verrouillé le spinlock */
void read_lock(rwlock_t *lock);
void read_lock_irqsave(rwlock_t *lock, unsigned long flags);
void read_lock_bh(rwlock_t *lock);

void read_unlock(rwlock_t *lock);
void read_unlock_irqsave(rwlock_t *lock, unsigned long flags);
void read_unlock_bh(rwlock_t *lock);

/* Version écrivain : bloquent tant que des lecteurs ou un autre
écrivain ont verrouillé le spinlock */
void write_lock(rwlock_t *lock);
void write_lock_irqsave(rwlock_t *lock, unsigned long flags);
void write_lock_bh(rwlock_t *lock);

void write_unlock(rwlock_t *lock);
void write_unlock_irqsave(rwlock_t *lock, unsigned long flags);
void write_unlock_bh(rwlock_t *lock);

Sémaphore

Le sémaphore est une autre primitive permettant de gérer l'accès concurrent à une ressource.

Schématiquement, il s'agit d'un compteur. Deux opérations sont possibles : * up : incrémente le compteur * down : si le compteur est strictement positif, il le décrémente et s'il est égal à zéro, bloque en mettant la tâche en sommeil jusqu'à ce qu'il soit de nouveau strictement positif puis le décrémente.

Un mutex est un sémaphore pour lequel le compteur ne peut prendre que les valeurs 0 ou 1.

Les opérations sur les sémaphores sont définies dans include/linux/semaphore.h.

/* Initialisation */
DEFINE_SEMAPHORE(sem);
/* ou */
struct semaphore sem;
void sema_init(struct semaphore *sem, int initial_val);

/* Opérations */

void down(struct semaphore *sem);
int down_interruptible(struct semaphore *sem);
int down_killable(struct semaphore *sem);
int down_trylock(struct semaphore *sem);
int down_timeout(struct semaphore *sem, long jiffies);

void up(struct semaphore *sem);

Problèmes classiques

L'utilisation de spinlocks ou de mutexes peut poser des problèmes d'interblocage (deadlock) :

La solution au second problème est de toujours verrouiller les ressources dans le même ordre (si par exemple il y a deux mutexes A et B, il faut décider par exemple de toujours verrouiller A puis B si jamais on a besoin de verrouiller les deux).

Ces problèmes ne sont pas spécifiques au noyau mais concernent toutes les applications mulithreads. Cependant, contrairement à une application qui serait bloquée, si tout ou partie du noyau est bloqué, il ne reste guère de solutions autres que de redémarrer.

D'autres mécanismes sont disponibles dans le noyau, comme par exemple RCU (Read Copy Update) mais ne seront pas décrits ici.

Travail à faire

  1. Reprenez les pilotes que vous avez écrits jusqu'à maintenant, réfléchissez aux éventuels problèmes d'accès concurrent aux diverses ressources (structures de données et matériel) et implémentez les mécanismes appropriés pour éviter les problèmes.

    Pour mémoire, plusieurs périphériques matériels peuvent être gérés par votre pilote (par exemple il pourrait y avoir plusieurs accéléromètres identiques sur le bus I2C avec simplement des adresses différentes), plusieurs applications peuvent avoir ouvert un même périphérique, etc.


  1. La fonction spin_lock_irqsave n'est pas une vraie fonction mais une macro, ce qui explique qu'elle puisse modifier flags alors qu'il n'est pas passé sous forme de pointeur.


Retour au sommaire du cours


© Copyright 2017 Guillaume Duc. Le contenu de cette page est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International (à l'exception des exemples de code tirés du noyau Linux et qui sont distribués sous leurs licences d'origine).

Licence
Creative Commons