Online Linux Driver Verification Service (alpha)

0060

RULE_ERROR

Inserting an element to a linked list if this element is already there

Summary

You should not invoke list_add() for an element, which is already in the list.

Description

A linked list is one of the most widespread data structures in the kernel. They are based on the structure list_head

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

The basic way to add a new element to the list is to use list_add() function:

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

The new argument is a pointer to a structure to be added to the list. The head argument is a pointer to the current head of the list.

Consider a situation when an element of a list is added to the list again. In this case the list_add() function modifies next and prev fields of the element, and, thus, brakes the old links. If the list looks like this before operation:

                              →a↔b↔c↔d↔e←

and we add the element c after the element a, we will have the list:

                           → a ↔ c ↔ b → c{↔ b} ← d ←

where {..} denotes the new link of the element c.

As a result, iteration along the list in the forward direction will lead to the infinite cycle. Therefore, you should not add a node to a list twice.

Links:

Samply bugfix in drivers/firmware/dmi_scan.c

Example

2.6.25 → drivers/firmware/dmi_scan.c