print · rss · source

< Quelques structures élémentaires pour gérer les fichiers | TutoOS | Gérer les 'Page Fault' >

Une méthode générique pour gérer les listes chaînées

Les sources

Le package contenant les sources est téléchargeable ici : kernel_LinkedList.tgz
Pour naviguer dans l'arborescence : LinkedList

Des listes de données

En langage C, l'organisation de données sous forme de liste peut être implémentée en utilisant un tableau ou une liste chaînée. L'utilisation de listes chaînées est très pratique car contrairement aux tableaux, les listes chaînées sont facilement extensibles et le retrait d'éléments se fait sans perte de mémoire. Les listes chaînées sont donc très utilisées par les noyaux et c'est aussi le cas de Pépin. Par exemple, nous avons définit dans le fichier mm.h une structure de donnée pour décrire une page mémoire. Cette structure contient deux attributs. Le champ v_addr correspond à l'adresse en mémoire virtuelle et le champ p_addr correspond à l'adresse en mémoire physique :

struct page {
        char *v_addr;
        char *p_addr;
};

Pour avoir une liste de pages, nous utilisons la structure struct page_list ci-dessous :

struct page_list {
        struct page *page;
        struct page_list *next;
        struct page_list *prev;
};

Ce type de liste est utilisé notamment par la struct page_directory, qui décrit un répertoire de pages et indique où sont les différentes tables de pages :

Cette méthode pour implémenter des listes chaînées présente deux inconvénients :

  • Le premier est que pour chaque type de donnée à chaîner, il faut créer un type particulier pour organiser la liste. Par exemple, pour faire une liste de processus, il faut créer un nouveau type struct process_list. Si nous voulons ensuite faire des listes de fichiers, alors il faut aussi un nouveau type et il en sera ainsi pour chaque type d'objet susceptible d'être organisé par liste.
  • Pour ajouter, insérer, enlever, déplacer ou rechercher un élément dans une liste, il est pratique de disposer de fonctions génériques pour ne pas avoir à réécrire à chaque fois les mêmes portions de code. Or, si nous utilisons à chaque fois des types particuliers pour effectuer le chaînage, nous sommes obligés d'utiliser à chaque fois des fonctions particulières.

Heureusement, les noyau Linux et FreeBSD proposent chacun une méthode pour implémenter de façon générique les listes chaînées. C'est ce que je vais essayer de présenter ci-dessous.

Les listes chaînées sous FreeBSD

Les systèmes d'exploitation de la famille *BSD utilisent une implémentation générique des listes chaînées située dans le fichier sys/queue.h. Cette implémentation, qui propose quatre types de listes, est décrite de façon détaillée sur http://www.freebsd.org/cgi/man.cgi?query=queue&sektion=3. Bien que la famille *BSD propose quatre types différents de listes, celles-ci partagent des caractéristiques communes :

  • la structure permettant le chaînage est intégrée à la structure des objets à chaîner
  • le programmeur décide du nom et du type de la structure permettant le chaînage
  • chaque liste est pointée par une "tête de liste"
  • la définition et la manipulation des listes repose uniquement sur un jeu de macro (cf. #define)

Le type SLIST

Le premier type de liste, le type SLIST, est une interface permettant de créer des listes simplement chaînées. Supposons que l'on veuille avoir une liste de struct something :

  • une structure anonyme permettant le chaînage est intégrée au sein de la structure
  • une tête de liste de type struct name pointe sur le premier élément

L'utilisation des macros pour gérer la liste est assez intuitive. Par exemple :

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

struct page {
    char *v_addr;
    char *p_addr;
    SLIST_ENTRY(page) plist;
};

void main(void)
{
     struct page *p1, *p2, *pp;
     SLIST_HEAD(my_pglist, page) pglist;            /* Declare the list. */

     SLIST_INIT(&pglist);                           /* Initialize the list. */

     p1 = malloc(sizeof(struct page));
     p1->v_addr = (char*) 0x1234;
     p1->p_addr = (char*) 0xffff1234;

     SLIST_INSERT_HEAD(&pglist, p1, plist);         /* Insert at the head. */

     p2 = malloc(sizeof(struct page));  
     p2->v_addr = (char*) 0x5678;
     p2->p_addr = (char*) 0xffff5678;

     SLIST_INSERT_AFTER(p1, p2, plist);             /* Insert after. */

     pp = SLIST_FIRST(&pglist);                     /* Get the first item */

     SLIST_FOREACH(pp, &pglist, plist)              /* Forward traversal. */
             printf("%p -> %p\n", pp->v_addr, pp->p_addr);

     SLIST_REMOVE(&pglist, p2, page, plist); /* Deletion. */
     free(p2);
}

Le type STAILQ

Le type STAILQ, est similaire au type précédent avec en plus un pointeur vers la fin de la liste, ce qui permet d'y ajouter un élément sans avoir à traverser toute la liste :

Le type LIST

Le type LIST est doublement chaîné de façon à ce que :

  • un élément puisse être enlevé sans avoir à traverser toute la liste
  • un élément puisse être inséré avant ou après n'importe quel autre élément sans avoir à traverser toute la liste
  • la liste puisse être parcourue dans les deux sens

Le type TAILQ

Le type TAILQ est similaire au type précédent avec en plus un pointeur vers la fin de la liste, ce qui permet d'y ajouter un élément sans avoir à traverser toute la liste :

Les listes chaînées sous Linux

Linux propose une implémentation très originale de liste circulaire doublement chaînée et dont les sources sont dans le fichier include/linux/list.h. Cette implémentation a certaines caractéristiques :

  • la structure permettant le chaînage est intégrée à la structure des objets à chaîner (c'est d'ailleurs le seul point commun avec les listes de type *BSD)
  • la tête de liste fait partie intégrante de la liste !
  • la structure permettant le chaînage est du type défini struct list_head
  • la définition et la manipulation des listes repose essentiellement sur un jeu de fonctions inline

Ce schéma fait apparaître une autre différence fondamentale entre l'implémentation de type *BSD et l'implémentation Linux. Dans l'implémentation *BSD, chaque structure de liste pointe sur l'objet suivant. Alors que dans l'implémentation Linux, chaque structure de liste pointe sur la structure de liste suivante. Dans l'implémentation Linux, nous avons donc une liste chaînée de structures de type list_head. Mais ce que nous voulons manipuler au final, ce sont bien les objets eux-mêmes : comment retrouver l'adresse d'un objet à partir du pointeur vers sa structure de liste ?

La fonction list_entry() fait ce travail :

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

Son implémentation repose sur une astuce expliquée dans les F.A.Q du langage C (question 2.14). Le schéma ci-dessous met en évidence la formule permettant de calculer l'offset entre l'adresse du début de la structure et l'adresse d'un membre en son sein :

L'utilisation des fonctions pour gérer ce type de liste est ensuite assez intuitive. Par exemple :

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct page {
    char *v_addr;
    char *p_addr;
    struct list_head plist;
};

void main(void)
{
     struct page *p1, *p2, *pp;
     struct list_head pglist, *l;

     INIT_LIST_HEAD(&pglist);                       /* Initialize the list. */

     p1 = malloc(sizeof(struct page));
     p1->v_addr = (char*) 0x1234;
     p1->p_addr = (char*) 0xffff1234;

     list_add(&p1->plist, &pglist);                 /* Insert after the head. */

     p2 = malloc(sizeof(struct page));  
     p2->v_addr = (char*) 0x5678;
     p2->p_addr = (char*) 0xffff5678;

     list_add(&p2->plist, &p1->plist);              /* Insert after */

     pp = list_first_entry(&pglist, struct page, plist); /* Get the first item */

     list_for_each(l, &pglist) {                    /* Forward traversal. */
         pp = list_entry(l, struct page, plist);
         printf("%p -> %p\n", pp->v_addr, pp->p_addr);
     }

     list_for_each_entry(pp, &pglist, plist)        /* Forward traversal again ! */
         printf("%p -> %p\n", pp->v_addr, pp->p_addr);

}
 

Les listes chaînées sous Pépin

Le noyau Pépin utilise la même implémentation de liste que pour le noyau Linux. Le code a été légèrement simplifié pour être rendu plus accessibles et le nombre de fonctions de manipulation de liste est moindre, mais fonctionnellement, les deux implémentations sont identiques : list.h

#ifndef __LIST__
#define __LIST__


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)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
        list->next = list;
        list->prev = list;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
        new->next = head->next;
        new->prev = head;
        head->next->prev = new;
        head->next = new;
}

static inline void list_del(struct list_head *p)
{
        p->next->prev = p->prev;
        p->prev->next = p->next;
        p->next = 0;
        p->prev = 0;
}

static inline int list_empty(const struct list_head *head)
{
        return head->next == head;
}

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

#define list_first_entry(head, type, member) \
        list_entry((head)->next, type, member)

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

#define list_for_each_safe(p, n, head) \
        for (p = (head)->next, n = p->next; p != (head); p = n, n = n->next)

#define list_for_each_entry(p, head, member)                            \
        for (p = list_entry((head)->next, typeof(*p), member);          \
             &p->member != (head);                                      \
             p = list_entry(p->member.next, typeof(*p), member))        \


#endif  /* __LIST__ */
[Get Code]

Le code du noyau a été entièrement réécrit en prenant en considération cette nouvelle implémentation. Même si celà a demandé un certain travail, de grandes portions de code ont pu être simplifiées. Par exemple, dans la fonction load_elf(), le code suivant :

if (get_p_addr((char *) v_addr) == 0) {
        if (pglist->page) {
                pglist->next = (struct page_list *) kmalloc(sizeof (struct page_list));
                pglist->next->next = 0;
                pglist->next->prev = pglist;
                pglist = pglist->next;
        }
        pglist->page = (struct page *) kmalloc(sizeof(struct page));
        pglist->page->p_addr = get_page_frame();
        pglist->page->v_addr = (char *) (v_addr & 0xFFFFF000);
        pd_add_page(pglist->page->v_addr, pglist->page->p_addr, PG_USER, pd);
}

a été remplacé par le code ci-dessous, plus court et donc un peu plus lisible :

if (get_p_addr((char *) v_addr) == 0) {
        pg = (struct page *) kmalloc(sizeof(struct page));
        pg->p_addr = get_page_frame();
        pg->v_addr = (char *) (v_addr & 0xFFFFF000);

        list_add(&pg->list, pglist);
        pd_add_page(pg->v_addr, pg->p_addr, PG_USER, pd);
}

< Quelques structures élémentaires pour gérer les fichiers | TutoOS | Gérer les 'Page Fault' >

print · rss · source
Page last modified on December 13, 2008, at 10:57 AM