list in linux kernel
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.
*** 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.
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».
list_add)list_add_tail)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;
}
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.
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);
}
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.
list_addLa 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».
list_for_each_entryDans 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);
}
de type struct student_entry * `.head devienne student_entry (c'est-à-dire la fin de la liste)
--Mettre à jour ʻitr avec l'élément de la liste avec ʻitr-> head.next (élément suivant de la liste)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