Table of Contents
If you're an engineer for Linux users, you're curious about how Linux works. I think there are many people who want to learn about the Linux kernel someday.
In this article, I'd like to take a look at the "list \ _head structure", a wall that beginners trying to get started with the Linux kernel may be at a loss early on.
This article was also posted on my blog https://achiwa912.github.io/.
First, get the source code of the Linux kernel.
Since the development of the Linux kernel has been going on for a long time, the code quoted in books etc. is already out of date. It's a good idea, so you want to get the latest version. Let's git clone the source code of the Linux kernel and bring it.
git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
It takes about 20-30 minutes. Let's leave it and wait.
~/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'
Congratulations. You now have a complete set of Linux kernel source code. It's surprisingly easy.
The Linux kernel is huge. I have no idea where to start. It's usually a good idea to use a Linux kernel book as in the references as a guide. By the way, I'm interested in VFS. That is inode or superblock. It may seem a little too sudden, but let's take a look at the data structure of superblock. It was in linux-stable / 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>
This is the superblock data structure. I have no idea what's inside. .. .. Focus on the first line in the structure.
struct list_head s_list; /* Keep this first */
This. list head structure. It's a tough guy that pushes beginners like me trying to read the kernel source code even a little. Moreover, a lot of them come out. In this article, I'd like to take a look at what this means.
The Linux kernel is written in C. Unlike more modern programming languages, the C language supports poor data structures and lacks object-oriented mechanics. For example, the list structure in Python etc. (such as ['abc','def']) is very convenient, and it is too easy to write a program, but there is no list in C language. Similarly, there are no classes in C. There are only structures.
Linux kernel developers are implementing these modern data structures in a unique way. One of them is the list head structure that realizes the list structure.
Now let's look at the definition of the list head structure. It is located in linux-stable / include / linux / types.h.
struct list_head {
struct list_head *next, *prev;
};
It's so simple that you can't beat it. It just contained pointers to the same list head structure as itself, forward and backward. I see, it's a two-way linked list. This is the one. (Strictly speaking, it is a circular bidirectional linked list)
+------+ +------+------+------+ +------+-----+------+ +------+
| null | <-> | prev | ... | next | <-> | prev | ... | next | <-> | null |
+------+ +------+------+------+ +------+-----+------+ +------+
No, please wait a moment. There is no point in listing even if it contains only the pointers before and after. If the data of each node that makes up the list is not included. For example, if you have an inode in a linked list, the inode should have a lot of data for the inode itself. File name, owner, permissions, etc. In the figure above, it is the part of ...
In fact, the list head structure is a handy one that allows you to link-list the embedded parent structure by embedding it in another structure. Wow! It is a change of thinking.
By the way, the superblock structure had a list head structure as a member.
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>
This makes the superblock a linked list node.
Furthermore, by embedding multiple list \ _head structures, it is possible to register to multiple linked lists at the same time. Just by looking at the definition of the struct, you can also see what it is in the linked list (because it has comments). This can't be imitated by Python links.
I understand the purpose of realizing a linked list in C language that does not have a list, but one problem remains. Wristhead structures only connect the same listhead structures together, but what you really want is a pointer to the parent structure in which it is embedded. I want to link the parent structure to a linked list.
A function is defined to do that.
/**
* 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)
The list \ _entry () function. These three arguments are
--ptr: Pointer to this list \ _head structure --type: The type of parent structure that embeds list \ _head (super \ _block in the above example) --member: The member name of this list \ _head structure in the parent structure (s \ _list in the above example)
And returns a pointer to the parent structure.
It was good, it was good. However, I am curious about the definition of the list \ _entry () function. What is container \ _of ()? When I searched with grep, there was a definition in linux-stable / 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))); })
Extract only the points.
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); })
First, the pointer to void \ _ \ _mptr is assigned by casting the pointer ptr to the list \ _head structure to the pointer to void. You can't use it as a pointer to the list \ _head structure.
In the next line, \ _ \ _mptr seems to be offset by offsetof (type, member) minutes. offsetof (type, member) is the offset of the member struct list \ _head s \ _list in the super \ _block structure in the above example. In other words, it was converting to a pointer to a parent super \ _block structure. And I'm casting this to a pointer to a super \ _block structure.
Summary,
It was that.
Note that container \ _of was defined as follows in the Linux Kernel Development in the references.
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
When I saw this, I was motivated to write this article because I was worried about "((type \ *) 0)-> member? What the hell is this doing ???" But with the latest sources, it's a little easier to understand.
If there is a structure in which the list \ _head structure is embedded in the data structure defined in the Linux kernel, you know that it is included in some linked list. If you read the comments in the source, you'll usually find what the linked list is.
You can use the list \ _entry () function to convert a pointer to a list \ _head structure to a pointer to the parent structure in which it is embedded. Then I took a look at the implementation of list \ _entry () --contaier \ _of () in the Linux kernel.
Recommended Posts