Linux Device Drivers, Second Edition

Linked Lists

Operating system kernels, like many other programs, often need to maintain lists of data structures. The Linux kernel has, at times, been host to several linked list implementations at the same time. To reduce the amount of duplicated code, the kernel developers have created a standard implementation of circular, doubly-linked lists; others needing to manipulate lists are encouraged to use this facility, introduced in version 2.1.45 of the kernel.

To use the list mechanism, your driver must include the file <linux/list.h>. This file defines a simple structure of type list_head:

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

Linked lists used in real code are almost invariably made up of some type of structure, each one describing one entry in the list. To use the Linux list facility in your code, you need only embed a list_head inside the structures that make up the list. If your driver maintains a list of things to do, say, its declaration would look something like this:

struct todo_struct {
    struct list_head list;
    int priority; /* driver specific */
    /* ... add other driver-specific fields */
};

The head of the list must be a standalone list_head structure. List heads must be initialized prior to use with the INIT_LIST_HEAD macro. A “things to do” list head could be declared and initialized with:

struct list_head todo_list;

INIT_LIST_HEAD(&todo_list);

Alternatively, lists can be initialized at compile time as follows:

LIST_HEAD(todo_list);

Several functions are defined in <linux/list.h> that work with lists:

list_add(struct list_head *new, struct list_head *head);

This function adds the new entry immediately after the list head—normally at the beginning of the list. It can thus be used to build stacks. Note, however, that the head need not be the nominal head of the list; if you pass a list_head structure that happens to be in the middle of the list somewhere, the new entry will go immediately after it. Since Linux lists are circular, the head of the list is not generally different from any other entry.

list_add_tail(struct list_head *new, struct list_head *head);

Add a new entry just before the given list head—at the end of the list, in other words. list_add_tail can thus be used to build first-in first-out queues.

list_del(struct list_head *entry);

The given entry is removed from the list.

list_empty(struct list_head *head);

Returns a nonzero value if the given list is empty.

list_splice(struct list_head *list, struct list_head *head);

This function joins two lists by inserting list immediately after head.

The list_head structures are good for implementing a list of like structures, but the invoking program is usually more interested in the larger structures that make up the list as a whole. A macro, list_entry, is provided that will map a list_head structure pointer back into a pointer to the structure that contains it. It is invoked as follows:

list_entry(struct list_head *ptr, type_of_struct, field_name);

where ptr is a pointer to the struct list_head being used, type_of_struct is the type of the structure containing the ptr, and field_name is the name of the list field within the structure. In our todo_struct structure from before, the list field is called simply list. Thus, we would turn a list entry into its containing structure with a line like this:

struct todo_struct *todo_ptr =
    list_entry(listptr, struct todo_struct, list);

The list_entry macro takes a little getting used to, but is not that hard to use.

The traversal of linked lists is easy: one need only follow the prev and next pointers. As an example, suppose we want to keep the list of todo_struct items sorted in descending priority order. A function to add a new entry would look something like this:

void todo_add_entry(struct todo_struct *new)
{
    struct list_head *ptr;
    struct todo_struct *entry;

    for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next) {
        entry = list_entry(ptr, struct todo_struct, list);
        if (entry->priority < new->priority) {
            list_add_tail(&new->list, ptr);
            return;
        }
    }
    list_add_tail(&new->list, &todo_struct)
}

The <linux/list.h> file also defines a macro list_for_each that expands to the for loop used in this code. As you may suspect, you must be careful when modifying the list while traversing it.

Figure 10-1 shows how the simple struct list_head is used to maintain a list of data structures.

Figure 10-1. The list_head data structure

Although not all features exported by the list.h as it appears in Linux 2.4 are available with older kernels, our sysdep.h fills the gap by declaring all macros and functions for use in older kernels.