Structures de données de type liste et leurs opérations dans le noyau Linux

list in linux kernel

Structure de données de type liste dans le noyau

Le noyau Linux est écrit en C, et il n'y a pas de liste standard en langage C. La façon de faire une liste dépend de la personne qui l'a mise en œuvre. Un code plus volumineux, tel que le noyau Linux, répertorie la normalisation. Son implémentation utilise pleinement les spécifications de langage particulières de C, et c'est assez difficile sans une certaine compréhension de C.

la mise en oeuvre

*** Une liste est implémentée en donnant une structure de données spéciale en tant que membre de la structure de données (structure) que vous voulez faire une liste. *** ***

struct student_entry {
    char    *name;
    int     num;
    struct list_head head;
};

Ci-après, cette structure de données sera utilisée comme exemple.

list_head list_head lui-même est une structure de données très simple, elle n'a que des pointeurs vers les éléments précédents et suivants.

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

En d'autres termes, seuls les «list_head» sont connectés en tant que liste. C'est un mécanisme très compliqué d'utiliser une structure qui l'a comme membre pour la faire fonctionner comme une liste.

Opération de liste

Initialisation

La liste est initialisée par la macro LIST_HEAD (nom). name spécifie le nom de la structure de données que vous souhaitez lister.

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

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

échantillon

LIST_HEAD(student_list);

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

Ceci définit les types d'éléments de la liste nommée «student_entry» et la liste nommée «student_list».

ajouter à

list_add La définition dans le noyau est un peu compliquée, alors écrivez-la un peu simple sans changer le comportement

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

échantillon

struct student_entry *e = malloc(sizeof(student_entry));
list_add(&e->head, &student_list);

list_add_tail Aussi un peu simplifié Ceux qui le connaissent remarqueront quelque chose, mais des détails seront donnés plus tard.

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

Effacer

list_del De l'élément précédent de la liste, suivant, à l'élément suivant, Supprimer de la liste en faisant de l'élément suivant de la liste prev l'élément précédent.

void list_del(struct list_head *entry) {
    struct list_head *next = entry->next, *prev = entry->prev;
    next->prev = prev;
    prev->next = next;
    next = LIST_POISON1;
    prev = LIST_POISON2;
}

En outre, entrez une valeur qui n'est pas "NULL" dans "next" et "prev" de l'élément à supprimer.

balayage

Il existe plusieurs analyses pour la liste et de nombreuses instructions for sont définies par des macros. Ici, nous allons expliquer en utilisant list_for_each_entry, qui opère sur chaque élément de la liste, à titre d'exemple.

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

Une instruction for qui affecte le premier élément de la liste spécifié dans pos et scanne jusqu'à la fin de la liste. échantillon

LIST_HEAD(student_list);

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

struct student_entry *e = malloc(sizeof(student_entry));
e->name = "hoge";
e->num = 1;
list_add(&e->head, &student_list);

struct student_entry *itr;
list_for_each_entry(itr, &student_list, head) {
    printf("%s %d\n", itr->name, itr->num);
}

macro

Si vous comprenez ce que j'ai expliqué ci-dessus, cela devrait suffire à l'utiliser. Mais je ne le comprends pas complètement. Je vais creuser dans les parties qui ont été simplifiées et expliquées.

Vrai list_add

La définition de list_add dans le noyau actuel est

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

Vous appelez «__list_add». Aussi, list_add_tail

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

Il appelle __list_add de la même manière, seuls les arguments sont différents. Alors qu'en est-il de __list_add?

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;

	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);
}

Le premier __list_add_valid, mais renvoie simplement true si CONFIG_DEBUG_LIST n'est pas défini.

#ifdef CONFIG_DEBUG_LIST
extern bool __list_add_valid(struct list_head *new, 
                struct list_head *prev,
                struct list_head *next);
#else
static inline bool __list_add_valid(struct list_head *new, 
                struct list_head *prev,
                struct list_head *next) {
    return true;
}

Le comportement lorsque CONFIG_DEBUG_LIST est défini est défini dans list_debug.c

bool __list_add_valid(struct list_head *new, struct list_head *prev,
		      struct list_head *next)
{
	if (CHECK_DATA_CORRUPTION(next->prev != prev,
			"list_add corruption. next->prev should be prev (%px), but was %px. (next=%px).\n",
			prev, next->prev, next) ||
	    CHECK_DATA_CORRUPTION(prev->next != next,
			"list_add corruption. prev->next should be next (%px), but was %px. (prev=%px).\n",
			next, prev->next, prev) ||
	    CHECK_DATA_CORRUPTION(new == prev || new == next,
			"list_add double add: new=%px, prev=%px, next=%px.\n",
			new, prev, next))
		return false;

	return true;
}

~~ C'est ennuyeux ~~

next-> prev! = prev`` prev-> next! = next`` new == Si l'un de prev est true, (dans certains cas, un avertissement est émis) et false est renvoyé. Ensuite, j'ai changé «suivant-> précédent» en «nouveau», etc.

	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);

Qu'est-ce que WRITE_ONCE?

static __always_inline void __write_once_size(volatile void *p, void *res, int size)
{
	switch (size) {
	case 1: *(volatile __u8 *)p = *(__u8 *)res; break;
	case 2: *(volatile __u16 *)p = *(__u16 *)res; break;
	case 4: *(volatile __u32 *)p = *(__u32 *)res; break;
	case 8: *(volatile __u64 *)p = *(__u64 *)res; break;
	default:
		barrier();
		__builtin_memcpy((void *)p, (const void *)res, size);
		barrier();
	}
}

#define WRITE_ONCE(x, val) \
({							\
	union { typeof(x) __val; char __c[1]; } __u =	\
		{ .__val = (__force typeof(x)) (val) }; \
	__write_once_size(&(x), __u.__c, sizeof(x));	\
	__u.__val;					\
})

En termes simples, la substitution est effectuée tout en empêchant une optimisation supplémentaire par gcc. Autrement dit, la signification essentielle ne change pas même si elle est lue comme «prev-> next = new».

Réel list_for_each_entry

Dans l'exemple list_for_each_entry (itr, & student_list, head) { La définition ne change pas.

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

Mais qu'en est-il de list_first_entry et list_next_entry dans ceci?

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

Et encore une fois l'emballage

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

Aussi un emballage. Et ce container_of est une macro de transformation fréquente très importante dans le noyau Linux Il est défini dans kernel.h.

#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

Immédiatement à nouveau macro Tout d'abord, BUILD_BUG_ON_MSG Comme son nom l'indique, si le premier argument est «true», un message d'erreur sera affiché au moment de la construction. Le premier argument est

!__same_type(*(ptr), ((type *)0)->member) && !__same_type(*(ptr), void)

__same_type est une macro qui renvoie si les arguments correspondent comme son nom l'indique. Donc cette ligne est

** Cause une erreur de construction lorsque les types de * ptr et ((type *) 0) -> membre sont différents et que * ptr n'est pas le type void **

La ligne suivante est essentielle

	((type *)(__mptr - offsetof(type, member))); })

__mptr cast to void * ptr Il y a une autre macro Comme son nom l'indique, ʻoffsetof trouve également le décalage de membredanstype avec membre`.

#define offsetof(type, member) ((size_t) &((type*)0)->member)

Par conséquent, une fois développé, container_of est

    ((type*)((void*)ptr - ((size_t) &((type*)0)->member)));

Pour le dire brièvement, ce que vous faites

*** Recherche d'un pointeur de type type avec ptr comme nom de membre ***

Ce serait bien si je pouvais comprendre cela. Revenez au sujet principal.

Pour comprendre list_for_each_entry, si vous développez la macro petit à petit

list_for_each_entry(itr, &student_list, head) {

Mais

for (itr = list_first_entry(&student_list, typeof(*itr), head);
        &itr->head != student_list;
        itr = list_next_entry(itr, head))

Et alors

for (itr = container_of((&student_list)->next, typeof(*itr), head);
        &itr->head != student_list;
        itr = container_of(itr->head.next, typeof(*itr), head))

Devient En d'autres termes, si vous développez un peu l'exemple de macro de code

struct list_head student_list { &student_list, &student_list};

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

struct student_entry *e = malloc(sizeof(student_entry));
e->name = "hoge";
e->num = 1;
list_add(&e->head, &student_list);

struct student_entry *itr;
for(itr = container_of((&student_list)->next, struct student_entry, head);
    &itr->head != student_list;
    itr = container_of(itr->head.next, struct student_entry, head)) {
    printf("%s %d\n", itr->name, itr->num);
}

sample code

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

struct list_head list_head;

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

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

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

#define offsetof(type, member) ((size_t) &((type *)0)->member)

#define container_of(ptr, type, member) ({      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type, member) );})

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

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

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

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

LIST_HEAD(student_list);

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

int main() {
    struct student_entry *a = malloc(sizeof(struct student_entry));
    a->name = "hoge";
    a->num = 1;
    struct student_entry *b = malloc(sizeof(struct student_entry));
    b->name = "fuga";
    b->num = 2;

    struct student_entry *itr;

    list_add(&b->head, &student_list);
    list_add(&a->head, &student_list);

    list_for_each_entry(itr, &student_list, head) {
        printf("%s %d\n", itr->name, itr->num);
    }
}

Recommended Posts

Structures de données de type liste et leurs opérations dans le noyau Linux
[Python] [Supplément] Chapitre 04-09 Structures de données diverses (théorie des ensembles et arithmétique dans les ensembles)
Notes sur la construction de TinyEMU et le démarrage du noyau Linux sur Emscripten
Résolution de l'introduction d'AOJ aux algorithmes et aux structures de données en Python -Partie1-
Résolution de l'introduction d'AOJ aux algorithmes et aux structures de données en Python -Partie2-
Résolution de l'introduction d'AOJ aux algorithmes et aux structures de données en Python -Partie4-
Résolution de l'introduction d'AOJ aux algorithmes et aux structures de données en Python -Partie3-
Essayez le mécanisme de verrouillage du noyau Linux
[Linux] [module du noyau] Créer kthread dans le module du noyau
Hashing de données en R et Python
Vérifiez le résumé des données dans CASTable
Remplacez le nom du répertoire et le nom du fichier dans le répertoire par une commande Linux.
[Comprendre en 3 minutes] Le début de Linux
Windows → Linux Conseils pour importer des données
Représentez facilement des données graphiques dans le shell et Python
Séparation de la conception et des données dans matplotlib
Trouvez-le dans la file d'attente et modifiez-le
Gérez les structures de données 3D avec les pandas
Compilation du noyau Linux (Linux 5.x sur Ubuntu 20.04)
[Python] Précautions lors de l'acquisition de données en grattant et en les mettant dans la liste
Je suis accro à la différence dans la façon dont Flask et Django reçoivent les données JSON
La première étape de l'analyse du journal (comment formater et mettre les données du journal dans Pandas)