I want to get started with the Linux kernel, what is the list head structure?

Table of Contents

  1. [Introduction](# org7dd38e2)
  2. [Obtain the source code](# org58d5983)
  3. [First step?](# Org092f94c)
  4. [list head structure](# orgffbcf4c)
  5. [Background](# org446ce82)
  6. [Definition of list head structure](# org64aa166)
  7. [Usage in Linux kernel](# org29687c0)
  8. Get a pointer to a parent structure (# org5c9d81b)
  9. [Summary](# orgda1c621)
  10. [References](# org9ca71bc)

Introduction

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/.

Obtaining the source code

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.

First step?

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.

list head structure

background

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.

list head structure definition

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 |
+------+     +------+------+------+     +------+-----+------+     +------+

How to use in Linux kernel

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.

Get a pointer to a parent structure

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,

  1. Cast the list \ _head structure to a pointer to void for ease of use
  2. Move the created pointer toward you so that it points to the beginning of the parent structure.
  3. Finally, cast to a pointer to the parent structure

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.

Summary

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.

References

Recommended Posts

I want to get started with the Linux kernel, what is the list head structure?
What I did to get started with Linux commands
I tried to get started with Bitcoin Systre on the weekend
I tried to get started with Hy
How to get started with laravel (Linux)
The easiest way to get started with Django
Get the latest Linux kernel version with Arch Linux
I want to get the path of the directory where the running file is stored.
5 Reasons Processing is Useful for Those Who Want to Get Started with Python
I want to be notified when the command operation is completed on linux!
I tried to get started with blender python script_Part 01
I tried to get started with blender python script_Part 02
I want to inherit to the back with python dataclass
What is Linux? [Command list]
I want to initialize if the value is empty (python)
Minimum knowledge to get started with the Python logging module
I want to get the operation information of yahoo route
I want to change the Japanese flag to the Palau flag with Numpy
What I did to welcome the Python2 EOL with confidence
[Python] I want to use the -h option with argparse
I tried to get started with Hy ・ Define a class
I want to make the Dictionary type in the List unique
Keras I want to get the output of any layer !!
I want to get the name of the function / method being executed
I want to know the weather with LINE bot feat.Heroku + Python
I tried to get the index of the list using the enumerate function
[Linux] I want to know the date when the user logged in
[Python] A memo that I tried to get started with asyncio
I wrote a script to get you started with AtCoder fast!
I want to output the beginning of the next month with Python
[Python] What is pip? Explain the command list and how to use it with actual examples
How to get started with Scrapy
How to get started with Python
How to get started with Django
What to do if the inode is exhausted on EC2 Linux
How to get a list excluding elements whose index is i ...?
For the time being, I want to convert files with ffmpeg !!
I want to do ○○ with Pandas
I want to check the position of my face with OpenCV!
What to do when you get "I can't see the site !!!!"
I want to debug with Python
What should I do with the Python directory structure after all?
[Introduction to Python] What is the difference between a list and a tuple?
[Linux] Command to get a list of commands executed in the past
I measured 6 methods to get the index of the maximum value (minimum value) of the list
I tried to get the authentication code of Qiita API with Python.
I want to sort a list in the order of other lists
I want to express my feelings with the lyrics of Mr. Children
I want to identify the alert email. --Is that x a wildcard? ---
I want to stop the automatic deletion of the tmp area with RHEL7
I tried to get the movie information of TMDb API with Python
[Introduction to Python] What is the method of repeating with the continue statement?
Step notes to get started with django
I want to detect objects with OpenCV
I want to know how LINUX works!
I want to blog with Jupyter Notebook
I want to use Linux on mac
I want to pip install with PythonAnywhere
I want to analyze logs with Python
I want to play with aws with python
Get started with the documentation tool Sphinx