Listed data structures in the Linux kernel and their operations

list in linux kernel

List-type data structures in the kernel

The Linux kernel is written in C, and there is no standard list in C. How to make a list depends on the person who implemented it. Larger code, such as the Linux kernel, does list standardization. Its implementation makes full use of C's peculiar language specifications, and it is quite difficult without some understanding of C.

Implementation

*** A list is implemented by giving a special data structure as a member to the data structure (structure) that you want to make a list. *** ***

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

Hereinafter, this data structure will be used as a sample.

list_head list_head itself is a very simple data structure, it just has pointers to the preceding and following elements.

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

In other words, only list_heads are connected as a list. It is a very complicated mechanism to use a structure that has it as a member to operate it as a list.

List operation

-Initialize -Add -Delete -[Scan](# Scan)

Initialization

Initialize the list with the macro LIST_HEAD (name). name specifies the name of the data structure you want to list.

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

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

sample

LIST_HEAD(student_list);

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

This defines the element types of the list named student_entry and the list named student_list.

add to

-[Add to the top of the list](# list_add) -[Add to end of list](# list_add_tail)

list_add The definition in the kernel is a little complicated, so write it a little simple without changing the behavior

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

sample

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

list_add_tail Also a little simplified Those who are familiar with it will notice something, but details will be given later.

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

Delete

list_del The next of the previous element in the list is the next element, Remove from the list by making prev, the next element in the list, the previous element.

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

Also, enter values that are not NULL in next and prev of the element to be deleted.

scanning

There are multiple scans on the list, and many for statements are defined by macros. Here, we will explain using list_for_each_entry, which operates on each element of the list, as an example.

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

A for statement that assigns the first element of the list specified in pos and scans to the end of the list. sample

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

macro

If you understand what I explained above, it should be enough to use. But I don't understand it completely. I will dig into the parts that have been simplified and explained.

Real list_add

The definition of list_add in the actual kernel is

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

You are calling __list_add. Also, list_add_tail

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

It calls __list_add in the same way, only the arguments are different. So what about __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);
}

The first __list_add_valid, but just returns true if CONFIG_DEBUG_LIST is not defined.

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

The behavior when CONFIG_DEBUG_LIST is defined is defined in list_debug.c

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

~~ It's annoying ~~

next-> prev! = prev`` prev-> next! = next new == If any of prev is true, (in some cases a warning is issued) and false is returned. Next, I changed next-> prev to new, etc.

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

What is 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;					\
})

Simply put, substitution is done while preventing extra optimization by gcc. That is, the essential meaning does not change even if it is read as prev-> next = new.

Real list_for_each_entry

In the sample list_for_each_entry (itr, & student_list, head) { The definition does not change.

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

But what about list_first_entry and list_next_entry in this?

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

And again the rapper

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

Also a rapper. And this container_of is a super important frequent transformation macro in the Linux kernel It is defined in kernel.h.

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

Immediately again macro First, BUILD_BUG_ON_MSG As the name suggests, if the first argument is true, an error message will be output at build time. The first argument is

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

__same_type is a macro that returns whether the arguments match as the name implies. So this line is

** Cause a build error when * ptr and ((type *) 0)-> member are of different types and * ptr is not of void type **

The next line is essential

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

__mptr is cast to void * `` ptr There is another macro As the name implies, ʻoffsetof also finds the offset of memberintype with member`.

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

Therefore, when expanded, container_of is

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

To put it briefly, what you are doing

*** I'm looking for a pointer of type type that has ptr with the member name member ***

It would be nice if I could understand this. Return to the main subject.

To understand list_for_each_entry, if you expand the macro little by little

list_for_each_entry(itr, &student_list, head) {

But

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

And then

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

Becomes In other words, if you expand the macro of the sample code a little

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

--Substitute the first element of the list for ʻitr of type struct student_entry * . --Until the address of head becomes student_entry (that is, the end of the list) --Update ʻitr with list element with ʻitr-> head.next` (next element of list)

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