Skip to content

Kernel Data Structure

References

[1] Linux Kernel Development, 3nd

Linked List

list_head: include/list.h#L24

The Linked List Structure

Linked list is popular data structure that is used in programming. The Linux Kernel approach is different. Instead of turning the structure into a linked list, the Linux approach is to embed a linked list noed in the structure!

The linked-list code is declared in the header file <linux/list.h> and the data structure is simple:

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

embed in a structure:

struct fox {
    unsigned long tail_length; /* length in centimeters of tail */
    unsigned long weight; /* weight in kilograms */
    bool is_fantastic; /* is this fox fantastic? */

    struct list_head list; /* list of all fox structures */
};

From a pointer that points to the struct list_head in a structure, we can get pointer to this structure by using macro list_entry (see container_of()):

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

Example:

    struct fox red_fox, *fox_ptr;                       // fox_ptr is pointing to nothing

    struct list_head *list_ptr = &red_fox.list;         // make list_ptr point to struct list inside red_fox
    fox_ptr = list_entry(list_ptr, struct fox, list);   // fox_ptr now is pointing to red_fox

Defining a Linked List

There are two ways to define a linked-list:

  • Defining listed-list with the first entry:

Dynamic Allocation, 

struct fox *red_fox;
red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL);
red_fox->tail_length = 40;
red_fox->weight = 6;
red_fox->is_fantastic = false;
INIT_LIST_HEAD(&red_fox->list);

And static alocation,

struct fox red_fox = {
    .tail_length = 40,
    .weight = 6,
    .list = LIST_HEAD_INIT(red_fox.list),
};
  • Defining a empty linked-list:

static LIST_HEAD(fox_list);

The second approach is used popularly in Linux Kernel (see spi.c).

Traversing Linked Lists

The kernel (thank goodness) provides a nice set of interfaces for traversing linked lists and referencing the data structures that include them.

The Basic Approach

struct list_head *p;
struct fox *f;

list_for_each(p, fox_list) {
    /* p points to an entry (struct list_head) in the list */

    f = list_entry(p, struct fox, list); // We need to use list_entry to get the "fox" structure
}

The Usable Approach

struct fox *f;

list_for_each_entry(f, &fox_list, list) {
    /* on each iteration, ‘f’ points to the next fox structure ... */
}

container_of()

container_of: include/linux/kerne.h#108

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

Assume that we have a structure:

struct data {
    int data1;
    int data2;
}

And a pointer int *child_ptr point to data2 which is a member of struct data. 

int *child_ptr = &data2;

We can user container_of() to get a pointer pointing to struct data.

struct data *data_ptr = container_of(child_ptr, struct container, data2);

Can we implement "container_of" in c for user space application?

Back to top