Table of Contents
Wenn Sie ein Linux-Anwender sind, sind Sie neugierig, wie Linux funktioniert. Ich denke, es gibt viele Leute, die eines Tages etwas über den Linux-Kernel lernen wollen.
In diesem Artikel möchte ich einen Blick auf die "list \ _head-Struktur" werfen, eine Wand, an der Anfänger, die versuchen, mit dem Linux-Kernel zu beginnen, möglicherweise frühzeitig ratlos sind.
Dieser Artikel wurde auch in meinem Blog https://achiwa912.github.io/ veröffentlicht.
Holen Sie sich zunächst den Quellcode für den Linux-Kernel.
Da die Entwicklung des Linux-Kernels schon lange andauert, ist der in Büchern usw. zitierte Code bereits veraltet. Es ist eine gute Idee, also möchten Sie die neueste Version erhalten. Lassen Sie uns den Quellcode des Linux-Kernels klonen und bringen.
git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
Es dauert ungefähr 20-30 Minuten. Lassen wir es und warten.
~/git % git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
Cloning into 'linux-stable'...
warning: redirecting to https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git/
remote: Enumerating objects: 1189260, done.
remote: Counting objects: 100% (1189260/1189260), done.
remote: Compressing objects: 100% (165947/165947), done.
remote: Total 8680156 (delta 1022459), reused 1186934 (delta 1020762), pack-reused 7490896
Receiving objects: 100% (8680156/8680156), 1.57 GiB | 3.01 MiB/s, done.
Resolving deltas: 100% (7328421/7328421), done.
Updating files: 100% (69365/69365), done.
warning: the following paths have collided (e.g. case-sensitive paths
on a case-insensitive filesystem) and only one from the same
colliding group is in the working tree:
'include/uapi/linux/netfilter/xt_CONNMARK.h'
'include/uapi/linux/netfilter/xt_connmark.h'
'include/uapi/linux/netfilter/xt_DSCP.h'
'include/uapi/linux/netfilter/xt_dscp.h'
'include/uapi/linux/netfilter/xt_MARK.h'
'include/uapi/linux/netfilter/xt_mark.h'
'include/uapi/linux/netfilter/xt_RATEEST.h'
'include/uapi/linux/netfilter/xt_rateest.h'
'include/uapi/linux/netfilter/xt_TCPMSS.h'
'include/uapi/linux/netfilter/xt_tcpmss.h'
'include/uapi/linux/netfilter_ipv4/ipt_ECN.h'
'include/uapi/linux/netfilter_ipv4/ipt_ecn.h'
'include/uapi/linux/netfilter_ipv4/ipt_TTL.h'
'include/uapi/linux/netfilter_ipv4/ipt_ttl.h'
'include/uapi/linux/netfilter_ipv6/ip6t_HL.h'
'include/uapi/linux/netfilter_ipv6/ip6t_hl.h'
'net/netfilter/xt_DSCP.c'
'net/netfilter/xt_dscp.c'
'net/netfilter/xt_HL.c'
'net/netfilter/xt_hl.c'
'net/netfilter/xt_RATEEST.c'
'net/netfilter/xt_rateest.c'
'net/netfilter/xt_TCPMSS.c'
'net/netfilter/xt_tcpmss.c'
'tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus'
'tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus'
Herzliche Glückwünsche. Sie haben jetzt einen vollständigen Satz von Linux-Kernel-Quellcode. Es ist überraschend einfach.
Der Linux-Kernel ist riesig. Ich habe keine Ahnung, wo ich anfangen soll. Es ist normalerweise eine gute Idee, ein Linux-Kernel-Buch wie in den Referenzen als Leitfaden zu verwenden. Ich interessiere mich übrigens für VFS. Das ist Inode oder Superblock. Es mag etwas zu plötzlich erscheinen, aber schauen wir uns die Datenstruktur von Superblock an. Es war in Linux-stabil / include / linux / fs.h.
struct super_block {
struct list_head s_list; /* Keep this first */
dev_t s_dev; /* search index; _not_ kdev_t */
unsigned char s_blocksize_bits;
unsigned long s_blocksize;
loff_t s_maxbytes; /* Max file size */
struct file_system_type *s_type;
const struct super_operations *s_op;
const struct dquot_operations *dq_op;
const struct quotactl_ops *s_qcop;
const struct export_operations *s_export_op;
unsigned long s_flags;
unsigned long s_iflags; /* internal SB_I_* flags */
unsigned long s_magic;
struct dentry *s_root;
struct rw_semaphore s_umount;
int s_count;
atomic_t s_active;
<snip>
Dies ist die Datenstruktur von Superblock. Ich habe keine Ahnung, was drin ist. .. .. Konzentrieren Sie sich auf die erste Zeile in der Struktur.
struct list_head s_list; /* Keep this first */
Dies. Listenkopfstruktur. Es ist ein harter Kerl, der Anfänger wie mich verdrängt, die den Quellcode des Kernels sogar ein wenig lesen wollen. Außerdem kommen viele von ihnen heraus. In diesem Artikel möchte ich einen Blick darauf werfen, was dies bedeutet.
Der Linux-Kernel ist in C-Sprache geschrieben. Im Gegensatz zu moderneren Programmiersprachen unterstützt die C-Sprache schlechte Datenstrukturen und enthält keinen objektorientierten Mechanismus. Zum Beispiel ist die Listenstruktur in Python usw. (wie ['abc', 'def']) sehr praktisch und es ist zu einfach, ein Programm zu schreiben, aber es gibt keine Liste in C-Sprache. Ebenso gibt es in C keine Klassen. Es gibt nur eine Struktur.
Linux-Kernel-Entwickler implementieren diese modernen Datenstrukturen auf einzigartige Weise. Eine davon ist die Listenkopfstruktur, die die Listenstruktur realisiert.
Schauen wir uns nun die Definition der Listenkopfstruktur an. Es befindet sich unter linux-stabil / include / linux / types.h.
struct list_head {
struct list_head *next, *prev;
};
Es ist so einfach, dass man es nicht schlagen kann. Es enthielt nur Zeiger auf dieselbe Listenkopfstruktur wie sich selbst, vorwärts und rückwärts. Ich sehe, es ist eine bidirektionale verknüpfte Liste. Das ist der eine. (Genau genommen handelt es sich um eine zirkuläre bidirektionale verknüpfte Liste.)
+------+ +------+------+------+ +------+-----+------+ +------+
| null | <-> | prev | ... | next | <-> | prev | ... | next | <-> | null |
+------+ +------+------+------+ +------+-----+------+ +------+
Nein, bitte warten Sie einen Moment. Es gibt keinen Punkt in einer Liste, selbst wenn sie nur die vorderen und hinteren Zeiger enthält. Wenn die Daten jedes Knotens, aus dem die Liste besteht, nicht enthalten sind. Wenn Sie beispielsweise einen Inode in einer verknüpften Liste haben, sollte der Inode viele eigene Daten des Inodes enthalten. Dateiname, Eigentümer, Berechtigungen usw. In der obigen Abbildung ist es der Teil von ...
Tatsächlich ist die Listenkopfstruktur praktisch, mit der Sie die eingebettete übergeordnete Struktur durch Einbetten in eine andere Struktur verknüpfen können. Beeindruckend! Es ist eine Änderung des Denkens.
Übrigens hatte die Superblock-Struktur eine Listenkopfstruktur als Mitglied.
struct super_block {
struct list_head s_list; /* Keep this first */
dev_t s_dev; /* search index; _not_ kdev_t */
unsigned char s_blocksize_bits;
<snip>
Auf diese Weise wird der Superblock zu einem verknüpften Listenknoten.
Darüber hinaus ist es durch Einbetten mehrerer List \ _head-Strukturen möglich, sich gleichzeitig in mehreren verknüpften Listen zu registrieren. Wenn Sie sich nur die Definition der Struktur ansehen, können Sie sehen, was und was es in der verknüpften Liste ist (weil es Kommentare enthält). Dies kann in Python-Links nicht nachgeahmt werden.
Ich verstehe den Zweck der Realisierung einer verknüpften Liste in C-Sprache, die keine Liste enthält, aber ein Problem bleibt. Handgelenkkopfstrukturen verbinden nur dieselben Listenkopfstrukturen miteinander, aber was Sie wirklich wollen, ist ein Zeiger auf die übergeordnete Struktur, in die sie eingebettet ist. Ich möchte die übergeordnete Struktur verknüpfen.
Dazu ist eine Funktion definiert.
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
Die Funktion list \ _entry (). Diese drei Argumente sind
--ptr: Zeiger auf diese List \ _head-Struktur --type: Der Typ der übergeordneten Struktur, in die list \ _head eingebettet ist (super \ _block im obigen Beispiel) --member: Der Mitgliedsname dieser List \ _head-Struktur in der übergeordneten Struktur (s \ _list im obigen Beispiel)
Und gibt einen Zeiger auf die übergeordnete Struktur zurück.
Es war gut, es war gut. Ich bin jedoch gespannt auf die Definition der Funktion list \ _entry (). Was ist Container \ _of ()? Als ich mit grep gesucht habe, gab es eine Definition in linux-stabil / include / linux / kernel.h.
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#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))); })
Extrahieren Sie nur die Punkte.
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); })
Zuerst wird der Zeiger auf void \ _ \ _mptr zugewiesen, indem der Zeiger ptr auf die List \ _head-Struktur in den Zeiger auf void umgewandelt wird. Sie können es nicht als Zeiger auf die List \ _head-Struktur verwenden.
In der nächsten Zeile scheint \ _ \ _mptr um den Versatz von (Typ, Element) Minuten versetzt zu sein. offsetof (Typ, Element) ist der Versatz der Elementstrukturliste \ _head s \ _list in der Super \ _block-Struktur im obigen Beispiel. Mit anderen Worten, es wurde in einen Zeiger auf die übergeordnete Super \ _block-Struktur konvertiert. Und ich verwandle dies in einen Zeiger auf eine Super \ _block-Struktur.
Zusammenfassung,
Es war das.
Beachten Sie, dass der Container \ _of in der Linux-Kernel-Entwicklung in der Referenz wie folgt definiert wurde.
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
Als ich das sah, machte ich mir Sorgen um "((Typ \ *) 0) -> Mitglied? Was zum Teufel macht das ???", was die Motivation für das Schreiben dieses Artikels war. In der neuesten Quelle war es jedoch etwas einfacher zu verstehen.
Wenn es eine Struktur gibt, in der die list \ _head-Struktur in die im Linux-Kernel definierte Datenstruktur eingebettet ist, wissen Sie, dass sie in einer verknüpften Liste enthalten ist. Wenn Sie die Kommentare in der Quelle lesen, finden Sie normalerweise die verknüpfte Liste.
Mit der Funktion list \ _entry () können Sie einen Zeiger auf die Struktur list \ _head in einen Zeiger auf die übergeordnete Struktur konvertieren, in die er eingebettet ist. Dann habe ich mir die Implementierung von list \ _entry () --contaier \ _of () im Linux-Kernel angesehen.