Why do most linked list looping macros in the kernel skip the first element?

user_7134737 0
Viewed 337

I might be wrong but keep looking at the code in <linux/list.h> and I see that macros like list_for_each_entry_safe starting from the second element:

#define list_for_each_entry_safe(pos, n, head, member)          \
    for (pos = list_entry((head)->next, typeof(*pos), member),  \
        n = list_entry(pos->member.next, typeof(*pos), member); \
         &pos->member != (head);                    \
         pos = n, n = list_entry(n->member.next, typeof(*n), member))

Notice that the loop starts with pos = list_entry((head)->next.

I know this may sound nit-picky but in a "true" foreach like in Python you start with the first or 0th element.

Is there any particular reason that this convention is violated in the kernel ? Is it for performance reasons ?

Or is my understanding of the above code completely wrong ?

linux-kernel linked-list foreach linux c
2 Answers

The kernel's list type is an intrusive data structure, where the list element structure is included within the data elements of the list, rather than being an external list that contains the data elements (or pointers to them) within the list elements.

The first (head) element of the list is not included within a data element, however. Instead, it is included within the data structure that owns the list (which is likely of a different type to the data elements). This means that when iterating over the data elements of the list, you don't include the list head (because it's not contained within a data element at all).

For example, struct device (defined in linux/device.h) contains a field struct list_head msi_list;. This is the head of a list of struct msi_desc (defined in linux/msi.h), and struct msi_desc contains a corresponding field struct list_head list;. The list of MSI descriptors is composed of a linked list of struct list_head elements, but the head element is the msi_list field of a struct device, whereas the other elements are each list elements of a struct msi_desc. When iterating over the list, we only want to iterate over the struct msi_desc data elements (we already have the struct device - that's how we got the head of the list in the first place).

user_1346330

head is a head of the list itself, not the first element of the list. And head->next is actually a way to refer to the list's first element.

For example, below is a definition of the macro which returns the first entry of the list:

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