Datenstrukturen vom Listentyp und ihre Operationen im Linux-Kernel

list in linux kernel

Listentyp-Datenstruktur im Kernel

Der Linux-Kernel ist in C geschrieben, und es gibt keine Standardliste in C-Sprache. Wie eine Liste erstellt wird, hängt von der Person ab, die sie implementiert hat. Größerer Code wie der Linux-Kernel listet die Standardisierung auf. Die Implementierung nutzt die besonderen Sprachspezifikationen von C vollständig aus und ist ohne ein gewisses Verständnis von C ziemlich schwierig.

Implementierung

*** Eine Liste wird implementiert, indem der Datenstruktur (Struktur), für die Sie eine Liste erstellen möchten, eine spezielle Datenstruktur als Mitglied zugewiesen wird. *** ***

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

Im Folgenden wird diese Datenstruktur als Beispiel verwendet.

list_head list_head selbst ist eine sehr einfache Datenstruktur, sie enthält nur Zeiger auf die vorhergehenden und folgenden Elemente.

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

Mit anderen Worten, nur list_heads werden als Liste verbunden. Es ist ein sehr komplizierter Mechanismus, eine Struktur zu verwenden, die sie als Mitglied hat, um sie als Liste zu betreiben.

Listenoperation

• Initialisieren
• Hinzufügen
• [Löschen](# Löschen)
• [Scan](# Scan)

Initialisieren

Die Liste wird durch das Makro "LIST_HEAD (Name)" initialisiert. name gibt den Namen der Datenstruktur an, die Sie auflisten möchten.

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

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

Stichprobe

LIST_HEAD(student_list);

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

Dies definiert die Elementtypen der Liste mit dem Namen "student_entry" und der Liste mit dem Namen "student_list".

hinzufügen

• [Zum Anfang der Liste hinzufügen](# list_add)
• [Zum Ende der Liste hinzufügen](# list_add_tail)

list_add Die Definition im Kernel ist etwas kompliziert, schreiben Sie sie also etwas einfach, ohne das Verhalten zu ändern

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;
}

Stichprobe

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

list_add_tail Auch etwas vereinfacht Diejenigen, die damit vertraut sind, werden etwas bemerken, aber Details werden später gegeben.

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;
}

Löschen

list_del Vom vorherigen Element der Liste, "next", zum nächsten Element, Entfernen Sie aus der Liste, indem Sie "prev", das nächste Element in der Liste, zum vorherigen Element machen.

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;
}

Geben Sie außerdem einen Wert ein, der nicht "NULL" in "next" und "prev" des zu löschenden Elements ist.

Scannen

Es gibt mehrere Scans für die Liste, und viele für Anweisungen werden durch Makros definiert. Hier erklären wir als Beispiel "list_for_each_entry", das für jedes Element der Liste gilt.

#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))

Eine for-Anweisung, die das erste in pos angegebene Element der Liste zuweist und am Ende der Liste scannt. Stichprobe

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);
}

Makro

Wenn Sie verstehen, was ich oben erklärt habe, sollte es ausreichen, um zu verwenden. Aber ich verstehe es nicht ganz. Ich werde mich mit den Teilen befassen, die vereinfacht und erklärt wurden.

Echtes list_add

Die Definition von list_add im eigentlichen Kernel lautet

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

Sie rufen __list_add auf. Auch list_add_tail

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

Es ruft __list_add auf die gleiche Weise auf, nur die Argumente sind unterschiedlich. Was ist also mit __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);
}

Die erste __list_add_valid, gibt aber nur true zurück, wenn CONFIG_DEBUG_LIST nicht definiert ist.

#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;
}

Das Verhalten bei der Definition von "CONFIG_DEBUG_LIST" ist in "list_debug.c" definiert

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;
}

~~ Es ist nervig ~~

next-> prev! = prev`` prev-> next! = next`` new == Wenn einer von prev`` true ist (in einigen Fällen wird eine Warnung ausgegeben) und false zurückgegeben wird. Als nächstes habe ich "next-> prev" in "new" usw. geändert.

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

Was ist "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;					\
})

Einfach ausgedrückt erfolgt die Substitution unter Vermeidung einer zusätzlichen Optimierung durch gcc. Das heißt, die wesentliche Bedeutung ändert sich nicht, selbst wenn sie als "prev-> next = new" gelesen wird.

Echte list_for_each_entry

Im Beispiel list_for_each_entry (itr, & student_list, head) { Die Definition ändert sich nicht.

#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))

Aber was ist mit "list_first_entry" und "list_next_entry"?

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

Und wieder die Hülle

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

Auch ein Wrapper. Und dieses "container_of" ist ein sehr wichtiges häufiges Transformationsmakro im Linux-Kernel Es ist in kernel.h definiert.

#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))); })

Sofort wieder Makro Zuerst "BUILD_BUG_ON_MSG" Wie der Name schon sagt, wird beim Erstellen eine erste Fehlermeldung ausgegeben, wenn das erste Argument "true" ist. Das erste Argument ist

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

__same_type ist ein Makro, das zurückgibt, ob die Argumente übereinstimmen, wie der Name schon sagt. Also diese Linie ist

** Verursacht einen Build-Fehler, wenn die Typen "* ptr" und "((Typ ) 0) -> member" unterschiedlich sind und " ptr" nicht der Typ "void" ist **

Die nächste Zeile ist wichtig

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

__mptr wird in void * ptr umgewandelt Es gibt noch ein anderes Makro Wie der Name schon sagt, findet "offsetof" auch den Offset von "member" in "type" mit "member".

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

Wenn es erweitert wird, ist "container_of" daher

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

Um es kurz zu machen, was Sie tun

*** Ich suche einen Zeiger vom Typ type mit ptr als Mitgliedsnamen ***

Es wäre schön, wenn ich das verstehen könnte. Kehren Sie zum Hauptthema zurück.

Um list_for_each_entry zu verstehen, wenn Sie das Makro nach und nach erweitern

list_for_each_entry(itr, &student_list, head) {

Aber

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

Und dann

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

Wird Mit anderen Worten, wenn Sie das Beispielcode-Makro ein wenig erweitern

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);
}

• Ersetzen Sie das erste Element der Liste durch "itr" vom Typ "struct student_entry *".
• Bis die Adresse von "head" zu "student_entry" wird (dh das Ende der Liste)
• Aktualisiere itr mit dem Element der Liste mit itr-> head.next (das nächste Element der 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);
    }
}