Week02 List Notes

Further Reading

Doubly Linked List Implementation in the Linux Kernel

Linux uses a simple struct list_head to cleverly implemented a general ciruclar doubly linked list for many other structs.

// <linux/types.h>
struct list_head {
    struct list_head *next, *prev;
};

Operations

operations defined in <linux/list.h>

Initialisation

initialize the sentinel of a list to create an empty list

static

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

dynamic

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	WRITE_ONCE(list->next, list);
	WRITE_ONCE(list->prev, list);
}

list_add

Adds an entry to the front of a list

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);
}

list_add_tail

Adds an entry to the back of a list

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

list_del

Deletes an entry from a list

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	WRITE_ONCE(prev->next, next);
}

You are suggest to read <linux/list.h> for other list operation implementations.

Find the container

Use the address of the list node, you can dedude the address of the container struct using the macro container_of.

struct my_struct {
    // you can even put list_head in the middle of your struct
    struct list_head list;
    /* user specific fields */
    // ...
};

Doubly linked list with the list_head data structure

Using container_of in <linux/container_of.h>

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

offsetof() in <linux/stddef.h> returns the byte offset of the field member from the start of the structure type.

#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)

Further reading:

The Magical container_of() Macro

List in Linux Process Management

The extremely important data stucture task_struct

Processe are created by spawns

Further reading

Linux Device Drivers, Second EditionO’Reilly Online Learning

linux/include/linux/list.h at master · torvalds/linuxGitHub

<linux/list.h>

Doubly Linked List in Linux Source and The "container_of" MacroMedium