Adding items to a Linux kernel linked list

Question

I am using linux/list.h in my code for implementing queue/stack behavior. The API for adding at head/tail is as below:

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

Similar is for list_add_tail. Surprisingly, it returns nothing (void), so does it mean that addition to list in kernel using this API is always successful. I know that there is no concept of full here but what if memory allocation for new node is not available and other possible reasons?

Answer 1

The list API does not dynamically allocate any memory. I found this thing a bit puzzling, myself. Problem here is that Linux is written in C, not C++, but implements things in a quite object-oriented way, but in C it looks like inside out. It works as follows (this applies to several other Linux APIs, too, e.g. kobj):

You define some struct, which should be member of a list. In opposite of how you would usually think of linked lists, this object won't be put into the list by allocating some opaque list item and have a pointer pointing to your actual object, you make struct list_head an actual a member of your struct:

struct something {
    struct list_head list;
    uint8_t some_datum;
    uint16_t some_other_datum;
    void *a_pointer;
};

Your list will be some standalone struct list_head:

static LIST_HEAD(list_of_somethings);

To add elements to list_of_somethings you now would do something like

struct something *s = kmalloc(sizeof(*s), GFP_KERNEL);
s->some_datum = 23;
s->some_other_datum = 0xdeadbeef;
s->a_pointer = current;
list_add(&s->list, &list_of_somethings);

In other words, you have the element allocated already. This looks completely weird, but is elegant as f*ck. This "design-pattern" allows to have type-opaque lists in C, which would not be easy to do in another way: A list on its own is just a bunch of struct list_heads pointing to each other. As you know which actual struct you are expeting as a programmer, you know which element of this struct is the actual list_head and can use the container_of macro to get the pointer to the eventual struct you put into the list:

struct list_head *p = &list_of_somethings.next;
struct something *s = container_of(p, struct something, list);
pr_notice("some data = %i\n", s->some_data);

Notice that the actual struct list_head representing the list itself is handled specially by the iteration macros defined in <linux/list.h>, i.e.

#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

The address of list_of_somethings will be used to determine whether iterating reached the end of the list (or actually the list-object again). This is also the reason, why an empty list is defined as having next and prev point to the struct list_head itself.

I needed some time to wrap my head around this, too. ;)