Traversing Linked Lists

Now you know how to declare, initialize, and manipulate a linked list in the kernel. This is all very well and good, but it is meaningless if you have no way to access your data! The linked lists are just containers that holds your important data; you need a way to use lists to move around and access the actual structures that contain the data. The kernel (thank goodness) provides a very nice set of interfaces for traversing linked lists and referencing the data structures that include them.

Note that, unlike the list manipulation routines, iterating over a linked list in its entirety is clearly an O(n) operation, for n entries in the list.

The simplest way to iterate over a list is with the list_for_each() macro. The macro takes two parameters, both list_head structures. The first is a pointer used to point to the current entry; it is a temporary variable that you must provide. The second is a list_head in the list you want to traverse. On each iteration of the loop, the first parameter points to the next entry in the list, until each entry has been visited. Usage is as follows:

struct list_head *p;

list_for_each(p, list) {
        /* p points to an entry in the list */
}

Well, that is still worthless! A pointer to the list structure is usually no good; what we need is a pointer to the structure that contains the list. For example, with the previous my_struct example, we want a pointer to each my_struct, not a pointer to the list member in the structure. The macro list_entry() is provided, which returns the structure that contains a given list_head. It takes three parameters: a pointer to the given element, the type of structure in which the list is embedded, and the member name of the list within that structure.

Consider the following example:

struct list_head *p;
struct my_struct *my;

list_for_each(p, &mine->list) {
        /* my points to the structure in which the list is embedded */
        my = list_entry(p, struct my_struct, list);
}

The list_for_each() macro expands to a simple for loop. For example, the previous use expands to

for (p = mine->list->next; p != mine->list; p = p->next)

The list_for_each() macro also uses processor prefetching, if the processor supports such a feature, to prefetch subsequent entries into memory before they are actually referenced. Prefetching improves memory bus utilization on modern pipelined processors. To not perform prefetching, the macro __list_for_each() works just identically to this for loop. Unless you know the list is very small or empty, you should always use the prefetching version. You should never hand code the loop; always use the provided macros.

If you need to iterate through the list backward, you can use list_for_each_prev(), which follows the prev pointers instead of the next pointer.

Note that nothing prevents removal of list entries from the list while you are traversing it. Normally, the list needs some sort of lock to prevent concurrent access. The macro list_for_each_safe(), however, uses temporary storage to make traversing the list safe from removals:

struct list_head *p, *n;
struct my_struct *my;
list_for_each_safe(p, n, &mine->list) {
        /* my points to each my_struct in the list */
        my = list_entry(p, struct my_struct, list);
}

This macro provides protection from only removals. You probably require additional locking protection to prevent concurrent manipulation of the actual list data.