Detaillierte Analyse der verknüpften Liste des Linux-Kernels

1. Einführung in die Datenstruktur verknüpfter Listen

Verknüpfte Liste ist eine häufig verwendete Datenstruktur zum Organisieren geordneter Daten. Es verbindet eine Reihe von Datenknoten über Zeiger zu einer Datenkette und ist eine wichtige Implementierungsmethode für lineare Tabellen. Im Vergleich zu Arrays sind verknüpfte Listen dynamischer. Beim Erstellen einer verknüpften Liste ist es nicht erforderlich, die Gesamtdatenmenge im Voraus zu kennen, der Speicherplatz kann zufällig zugewiesen werden und Daten können an jeder Stelle der verknüpften Liste in Echtzeit effizient eingefügt oder gelöscht werden. Der Hauptaufwand verknüpfter Listen ist die Reihenfolge des Zugriffs und der Platzverlust bei der Organisation der Kette.

Im Allgemeinen sollte eine Datenstruktur einer verknüpften Liste mindestens zwei Felder enthalten: Datenfeld und Zeigerfeld. Das Datenfeld dient zum Speichern von Daten und das Zeigerfeld zum Herstellen des Kontakts mit dem nächsten Knoten. Abhängig von der Organisation des Zeigerfelds und der Verbindungsform zwischen den einzelnen Knoten kann die verknüpfte Liste in verschiedene Typen unterteilt werden, z. B. eine einfach verknüpfte Liste, eine doppelt verknüpfte Liste, eine zirkulär verknüpfte Liste usw. Im Folgenden finden Sie schematische Diagramme dieser gängigen verknüpften Listentypen:

1. Einzelne verknüpfte Liste

Einfach verknüpfte Liste ist die einfachste Art einer verknüpften Liste. Ihr Merkmal ist, dass es nur ein Zeigerfeld gibt, das auf den nachfolgenden Knoten (next) zeigt. Daher kann die einfach verknüpfte Liste nur sequentiell vom Anfang bis zum Ende durchlaufen werden (normalerweise NULL-Zeiger). ).

2． Doppelt verknüpfte Liste 3

Durch die Gestaltung der beiden Zeigerfelder Vorgänger und Nachfolger kann die doppelt verknüpfte Liste in zwei Richtungen durchlaufen werden, was sie von der einfach verknüpften Liste unterscheidet. Wenn die Abhängigkeitsbeziehung zwischen Vorgänger und Nachfolger gestört ist, kann ein „Binärbaum“ gebildet werden, wenn der Vorgänger des ersten Knotens auf den Endknoten der verknüpften Liste zeigt und der Nachfolger des Endknotens auf den ersten Knoten (wie in der gepunkteten Linie in Abbildung 2 dargestellt) wird eine kreisförmige verknüpfte Liste erstellt. Wenn mehr Zeigerfelder entworfen werden, können verschiedene komplexe baumartige Datenstrukturen gebildet werden.

3. Zirkuläre verknüpfte Liste

Das Merkmal einer zirkulär verknüpften Liste besteht darin, dass der Nachfolger des Endknotens auf den ersten Knoten zeigt. Das schematische Diagramm einer doppelten zirkulären verknüpften Liste wurde bereits beschrieben. Ihr Merkmal besteht darin, dass ausgehend von jedem Knoten und in beide Richtungen alle Daten in der verknüpften Liste gefunden werden können. Wenn der Vorgängerzeiger entfernt wird, handelt es sich um eine einzelne zirkulär verknüpfte Liste.

Eine große Anzahl verknüpfter Listenstrukturen wird im Linux-Kernel zum Organisieren von Daten verwendet, einschließlich Gerätelisten und Datenorganisation in verschiedenen Funktionsmodulen. Die meisten dieser verknüpften Listen verwenden eine wunderbare Datenstruktur für verknüpfte Listen, die in [include/linux/list.h] implementiert ist. In den folgenden Abschnitten dieses Artikels werden die Organisation und Verwendung dieser Datenstruktur anhand von Beispielen ausführlich vorgestellt.

2. Implementierung der Linux 2.6-Kernel-Datenstruktur für verknüpfte Listen

Obwohl hier der 2.6-Kernel als Grundlage für die Erklärung verwendet wird, unterscheidet sich die verknüpfte Listenstruktur im 2.4-Kernel tatsächlich nicht von der in 2.6. Der Unterschied besteht darin, dass 2.6 zwei Datenstrukturen verknüpfter Listen erweitert: Lesekopie-Aktualisierung der verknüpften Liste (rcu) und HASH-verknüpfte Liste (hlist). Beide Erweiterungen basieren auf der grundlegendsten Listenstruktur. Daher wird in diesem Artikel hauptsächlich die grundlegende Struktur verknüpfter Listen vorgestellt und anschließend kurz RCU und Hlist vorgestellt.

Die Definition der Datenstruktur der verknüpften Liste ist sehr einfach (Auszug aus [include/linux/list.h], alle folgenden Codes stammen, sofern nicht anders angegeben, aus dieser Datei):

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

Die list_head-Struktur enthält zwei Zeiger prev und next, die auf die list_head-Struktur verweisen. Es ist ersichtlich, dass die verknüpfte Liste des Kernels die Funktion einer doppelt verknüpften Liste hat. Tatsächlich ist sie normalerweise in einer doppelten verknüpften Liste organisiert.

Im Gegensatz zum im ersten Abschnitt vorgestellten Modell der doppelt verknüpften Listenstruktur verfügt list_head hier über kein Datenfeld. In der verknüpften Liste des Linux-Kernels sind die Knoten der verknüpften Liste nicht in der Struktur der verknüpften Liste enthalten, sondern in der Datenstruktur.

In Lehrbüchern zur Datenstruktur lautet die klassische Definition einer verknüpften Liste normalerweise wie folgt (am Beispiel einer einfach verknüpften Liste):

struct list_node {
 struct list_node *next;
 ElemType data;
};

Aufgrund von ElemType muss jeder Datenelementtyp seine eigene verknüpfte Listenstruktur definieren. Erfahrene C++-Programmierer sollten wissen, dass die Standardvorlagenbibliothek C++-Vorlagen verwendet, die Vorlagen verwenden, um verknüpfte Listenoperationsschnittstellen zu abstrahieren, die unabhängig von Datenelementtypen sind.

在Linux内核链表中，需要用链表组织起来的数据通常会包含一个struct list_head成员，例如在[include/linux/netfilter.h]中定义了一个nf_sockopt_ops结构来描述Netfilter为某一协议族准备的getsockopt/setsockopt接口，其中就有一个（struct list_head list）成员，各个协议族的nf_sockopt_ops结构都通过这个list成员组织在一个链表中，表头是定义在[net/core/netfilter.c]中的nf_sockopts（struct list_head）。从下图中我们可以看到，这种通用的链表结构避免了为每个数据项类型定义自己的链表的麻烦。Linux的简捷实用、不求完美和标准的风格，在这里体现得相当充分。

三、 链表操作接口

\1. 声明和初始化

实际上Linux只定义了链表节点，并没有专门定义链表头，那么一个链表结构是如何建立起来的呢？让我们来看看LIST_HEAD()这个宏：

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

当我们用LIST_HEAD(nf_sockopts)声明一个名为nf_sockopts的链表头时，它的next、prev指针都初始化为指向自己，这样，我们就有了一个空链表，因为Linux用头指针的next是否指向自己来判断链表是否为空：

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

除了用LIST_HEAD()宏在声明的时候初始化一个链表以外，Linux还提供了一个INIT_LIST_HEAD宏用于运行时初始化链表：

#define INIT_LIST_HEAD(ptr) do { /
 (ptr)->next = (ptr); (ptr)->prev = (ptr); /
} while (0)

我们用INIT_LIST_HEAD(&nf_sockopts)来使用它。

\2. 插入/删除/合并

a) 插入

对链表的插入操作有两种：在表头插入和在表尾插入。Linux为此提供了两个接口：

static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);

因为Linux链表是循环表，且表头的next、prev分别指向链表中的第一个和最末一个节点，所以，list_add和list_add_tail的区别并不大，实际上，Linux分别用

__list_add(new, head, head->next);

和

__list_add(new, head->prev, head);

来实现两个接口，可见，在表头插入是插入在head之后，而在表尾插入是插入在head->prev之后。

假设有一个新nf_sockopt_ops结构变量new_sockopt需要添加到nf_sockopts链表头，我们应当这样操作：

list_add(&new_sockopt.list, &nf_sockopts);

从这里我们看出，nf_sockopts链表中记录的并不是new_sockopt的地址，而是其中的list元素的地址。如何通过链表访问到new_sockopt呢？下面会有详细介绍。

b) 删除

static inline void list_del(struct list_head *entry);

当我们需要删除nf_sockopts链表中添加的new_sockopt项时，我们这么操作：

list_del(&new_sockopt.list);

被剔除下来的new_sockopt.list，prev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值，这样设置是为了保证不在链表中的节点项不可访问–对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相对应，list_del_init()函数将节点从链表中解下来之后，调用LIST_INIT_HEAD()将节点置为空链状态。

c) 搬移

Linux提供了将原本属于一个链表的节点移动到另一个链表的操作，并根据插入到新链表的位置分为两类：

static inline void list_move(struct list_head *list, struct list_head *head);
static inline void list_move_tail(struct list_head *list, struct list_head *head);

例如list_move(&new_sockopt.list,&nf_sockopts)会把new_sockopt从它所在的链表上删除，并将其再链入nf_sockopts的表头。

d) 合并

除了针对节点的插入、删除操作，Linux链表还提供了整个链表的插入功能：

static inline void list_splice(struct list_head *list, struct list_head *head);

假设当前有两个链表，表头分别是list1和list2（都是struct list_head变量），当调用list_splice(&list1,&list2)时，只要list1非空，list1链表的内容将被挂接在list2链表上，位于list2和list2.next（原list2表的第一个节点）之间。新list2链表将以原list1表的第一个节点为首节点，而尾节点不变。如图（虚箭头为next指针）：

图4 链表合并list_splice(&list1,&list2)

当list1被挂接到list2之后，作为原表头指针的list1的next、prev仍然指向原来的节点，为了避免引起混乱，Linux提供了一个list_splice_init()函数：

 static inline void list_splice_init(struct list_head *list, struct list_head *head);
 

该函数在将list合并到head链表的基础上，调用INIT_LIST_HEAD(list)将list设置为空链。

\3. 遍历

遍历是链表最经常的操作之一，为了方便核心应用遍历链表，Linux链表将遍历操作抽象成几个宏。在介绍遍历宏之前，我们先看看如何从链表中访问到我们真正需要的数据项。

a) 由链表节点到数据项变量

我们知道，Linux链表中仅保存了数据项结构中list_head成员变量的地址，那么我们如何通过这个list_head成员访问到作为它的所有者的节点数据呢？Linux为此提供了一个list_entry(ptr,type,member)宏，其中ptr是指向该数据中list_head成员的指针，也就是存储在链表中的地址值，type是数据项的类型，member则是数据项类型定义中list_head成员的变量名，例如，我们要访问nf_sockopts链表中首个nf_sockopt_ops变量，则如此调用：

list_entry(nf_sockopts->next, struct nf_sockopt_ops, list);

这里”list”正是nf_sockopt_ops结构中定义的用于链表操作的节点成员变量名。

list_entry的使用相当简单，相比之下，它的实现则有一些难懂：

#define list_entry(ptr, type, member) container_of(ptr, type, member)
container_of宏定义在[include/linux/kernel.h]中：
#define container_of(ptr, type, member) ({   /
        const typeof( ((type *)0)->member ) *__mptr = (ptr); /
        (type *)( (char *)__mptr - offsetof(type,member) );})
offsetof宏定义在[include/linux/stddef.h]中：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

size_t最终定义为unsigned int（i386）。

这里使用的是一个利用编译器技术的小技巧，即先求得结构成员在与结构中的偏移量，然后根据成员变量的地址反过来得出属主结构变量的地址。

container_of()和offsetof()并不仅用于链表操作，这里最有趣的地方是((type *)0)->member，它将0地址强制”转换”为type结构的指针，再访问到type结构中的member成员。在container_of宏中，它用来给typeof()提供参数（typeof()是gcc的扩展，和sizeof()类似），以获得member成员的数据类型；在offsetof()中，这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。

如果这么说还不好理解的话，不妨看看下面这张图：

图5 offsetof()宏的原理

对于给定一个结构，offsetof(type,member)是一个常量，list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。

b) 遍历宏

在[net/core/netfilter.c]的nf_register_sockopt()函数中有这么一段话：

  ……
struct list_head *i;
……
 list_for_each(i, &nf_sockopts) {
  struct nf_sockopt_ops *ops = (struct nf_sockopt_ops *)i;
  ……
 }
 ……
 

函数首先定义一个(struct list_head *)指针变量i，然后调用list_for_each(i,&nf_sockopts)进行遍历。在[include/linux/list.h]中，list_for_each()宏是这么定义的：

#define list_for_each(pos, head) /
 for (pos = (head)->next, prefetch(pos->next); pos != (head); /
         pos = pos->next, prefetch(pos->next))

它实际上是一个for循环，利用传入的pos作为循环变量，从表头head开始，逐项向后（next方向）移动pos，直至又回到head（prefetch()可以不考虑，用于预取以提高遍历速度）。

那么在nf_register_sockopt()中实际上就是遍历nf_sockopts链表。为什么能直接将获得的list_head成员变量地址当成struct nf_sockopt_ops数据项变量的地址呢？我们注意到在struct nf_sockopt_ops结构中，list是其中的第一项成员，因此，它的地址也就是结构变量的地址。更规范的获得数据变量地址的用法应该是：

struct nf_sockopt_ops *ops = list_entry(i, struct nf_sockopt_ops, list);

大多数情况下，遍历链表的时候都需要获得链表节点数据项，也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏：

#define list_for_each_entry(pos, head, member)  ……

与list_for_each()不同，这里的pos是数据项结构指针类型，而不是(struct list_head *)。nf_register_sockopt()函数可以利用这个宏而设计得更简单：

……
struct nf_sockopt_ops *ops;
list_for_each_entry(ops,&nf_sockopts,list){
 ……
}
……

某些应用需要反向遍历链表，Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作，使用方法和上面介绍的list_for_each()、list_for_each_entry()完全相同。

如果遍历不是从链表头开始，而是从已知的某个节点pos开始，则可以使用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求，即经过一系列计算后，如果pos有值，则从pos开始遍历，如果没有，则从链表头开始，为此，Linux专门提供了一个list_prepare_entry(pos,head,member)宏，将它的返回值作为list_for_each_entry_continue()的pos参数，就可以满足这一要求。

\4. 安全性考虑

在并发执行的环境下，链表操作通常都应该考虑同步安全性问题，为了方便，Linux将这一操作留给应用自己处理。Linux链表自己考虑的安全性主要有两个方面：

a) list_empty()判断

Das grundlegende list_empty() bestimmt nur, ob die verknüpfte Liste leer ist, basierend darauf, ob der nächste Kopfzeiger auf sich selbst zeigt. Die verknüpfte Linux-Liste stellt ein list_empty_careful()-Makro bereit, das gleichzeitig nur den nächsten und vorherigen Kopfzeiger bestimmt wenn beide auf sich selbst zeigen, wird nur dann true zurückgegeben. Dies dient hauptsächlich der Bewältigung der Situation, in der next und prev inkonsistent sind, weil eine andere CPU dieselbe verknüpfte Liste verarbeitet. Die Codekommentare geben jedoch auch zu, dass diese Sicherheitsgarantiefunktion begrenzt ist: Sofern die verknüpfte Listenoperation anderer CPUs nicht nur list_del_init () ist, kann die Sicherheit nicht garantiert werden, dh es ist weiterhin ein Sperrschutz erforderlich.

b) Knoten werden während der Durchquerung gelöscht

Mehrere Makros für das Durchlaufen verknüpfter Listen wurden bereits eingeführt. Sie alle erreichen den Zweck des Durchlaufens, indem sie den Pos-Zeiger bewegen. Wenn die Durchquerungsoperation jedoch das Löschen des Knotens umfasst, auf den der Pos-Zeiger zeigt, wird die Bewegung des Pos-Zeigers unterbrochen, da list_del(pos) das nächste und das vorherige von pos auf die Sonderwerte von LIST_POSITION2 und setzt LIST_POSITION1.

Natürlich kann der Aufrufer den nächsten Zeiger selbst zwischenspeichern, um die Durchlaufoperation kohärent zu machen, aber aus Gründen der Programmierkonsistenz stellen verknüpfte Linux-Listen immer noch zwei „_safe“-Schnittstellen bereit, die den grundlegenden Durchlaufoperationen entsprechen: list_for_each_safe(pos, n, head ), list_for_each_entry_safe(pos, n, head, member), erfordern sie, dass der Aufrufer einen weiteren Zeiger n vom gleichen Typ wie pos bereitstellt und die Adresse des nächsten Knotens von pos vorübergehend in der for-Schleife speichert, um durch die verursachte Fehler zu vermeiden Freigabe des POS-Knotens.

4. Erweiterung

1. hlist

Abbildung 6 Liste und Hlist

Der Linux-Designer verknüpfter Listen, der nach Exzellenz strebt (weil list.h nicht signiert ist, ist es also wahrscheinlich Linus Torvalds), glaubt, dass die doppelt verknüpfte Liste mit doppeltem Kopf (nächste, vorherige) „zu verschwenderisch“ für den HASH ist Daher entwarf er einen separaten Satz von HASH-Tabellen. Die in der HASH-Tabelle verwendete Datenstruktur ist eine doppelt zirkulär verknüpfte Liste mit Einzelzeiger-Headern. Wie aus der obigen Abbildung ersichtlich ist, verfügt der Hlist-Header nur über einen Zeiger auf den ersten Knoten Kein Zeiger auf den Endknoten. Dies kann ein massives Problem darstellen. Der in der HASH-Tabelle gespeicherte Header kann den Speicherplatzverbrauch um die Hälfte reduzieren.

Da die Datenstrukturen des Headers und des Knotens unterschiedlich sind, funktioniert die vorherige Methode nicht, wenn der Einfügevorgang zwischen dem Header und dem ersten Knoten erfolgt: Der erste Zeiger des Headers muss so geändert werden, dass er auf den neu eingefügten Knoten zeigt , kann aber nicht wie list_add( ) als einheitliche Beschreibung verwendet werden. Aus diesem Grund ist der prev des hlist-Knotens nicht mehr ein Zeiger auf den vorherigen Knoten, sondern ein Zeiger auf next (erster für den Header) im vorherigen Knoten (möglicherweise der Header) (struct list_head **pprev), also The Durch das Einfügen am Kopf der Tabelle kann über das konsistente „*(node->pprev)“ auf den nächsten (oder ersten) Zeiger des Vorgängerknotens zugegriffen und dieser geändert werden.

2. Lese-/Kopie-Update

Es gibt auch eine Reihe von Makros, die auf „_rcu“ enden, in der Linux-Funktionsschnittstelle für verknüpfte Listen, die vielen der oben vorgestellten Funktionen entsprechen. RCU (Read-Copy Update) ist eine neue Technologie, die im 2.5/2.6-Kernel eingeführt wurde und die Synchronisierungsleistung durch Verzögerung von Schreibvorgängen verbessert.

Wir wissen, dass es im System weit mehr Datenlesevorgänge als Schreibvorgänge gibt und die Leistung des RWlock-Mechanismus mit zunehmender Anzahl von Prozessoren in der SMP-Umgebung schnell abnimmt (siehe Referenz 4). Als Reaktion auf diesen Anwendungshintergrund schlug Paul E. McKenney vom IBM Linux Technology Center die „Read Copy Update“-Technologie vor und wendete sie auf den Linux-Kernel an. Der Kern der RCU-Technologie besteht darin, dass der Schreibvorgang in zwei Schritte unterteilt ist: Schreiben und Aktualisieren, was jederzeit einen entsperrten Zugriff für Lesevorgänge ermöglicht. Wenn das System einen Schreibvorgang ausführt, wird der Aktualisierungsvorgang verzögert, bis alle Lesevorgänge auf dem System ausgeführt werden Daten sind abgeschlossen. Die RCU-Funktion in der verknüpften Linux-Liste ist nur ein kleiner Teil der RCU-Implementierungsanalyse. Interessierte Leser können sich auf die Referenzmaterialien dieses Artikels und die Verwendung der RCU-verknüpften Liste beziehen Die Verwendung einer einfachen verknüpften Liste ist grundsätzlich dieselbe.

5. Beispiel

Das Programm im Anhang hat keine praktische Wirkung, außer dass es Dateien in Vorwärts- und Rückwärtsrichtung ausgeben kann. Es wird nur zur Demonstration der Verwendung von Linux-verknüpften Listen verwendet.

Der Einfachheit halber verwendet das Beispiel eine Programmvorlage im Benutzermodus. Wenn Sie es ausführen müssen, können Sie es mit dem folgenden Befehl kompilieren:

gcc -D__KERNEL__ -I/usr/src/linux-2.6.7/include pfile.c -o pfile

因为内核链表限制在内核态使用，但实际上对于数据结构本身而言并非只能在核态运行，因此，在笔者的编译中使用”-D__KERNEL__”开关”欺骗”编译器。

Das obige ist der detaillierte Inhalt vonDetaillierte Analyse der verknüpften Liste des Linux-Kernels. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!