CODEWITHSUNDEEP
clinux-kernellinked-list
satoru
satoru

Reputation: 33225

Correct way to join two double linked list

In the Linux kernel source, the list_splice is implemented with __list_splice:

static inline void __list_splice(const struct list_head *list,
                                 struct list_head *prev,
                                 struct list_head *next)
{
        struct list_head *first = list->next; // Why?
        struct list_head *last = list->prev;

        first->prev = prev;
        prev->next = first;

        last->next = next;
        next->prev = last;
}

Isn't the list already pointing to the head of a linked list? Why do we need to fetch list->next instead?

Upvotes: 9

Views: 615

Answers (1)

0andriy
0andriy

Reputation: 4674

The double linked list API in the Linux kernel is implemented as an abstraction of circular list. In that simple scheme the HEAD node does not contain any payload (data) and used explicitly to keep starting point of the list. Due to such design it's really simple to a) check if the list is empty, and b) debug list because unused nodes have been assigned to the so called POISON — magic number specific only to the list pointers in the entire kernel.

1) non-initialized list

+-------------+
|    HEAD     |
| prev | next |
|POISON POISON|
+-------------+

2) empty list

+----------+-----------+
|          |           |
|          |           |
|   +------v------+    |
|   |    HEAD     |    |
+---+ prev | next +----+
    | HEAD   HEAD |
    +-------------+

3) list with one element

+--------------+--------------+
|              |              |
|              |              |
|       +------v------+       |
|       |    HEAD     |       |
|   +---+ prev | next +--+    |
|   |   |ITEM1   ITEM1|  |    |
|   |   +-------------+  |    |
|   +--------------------+    |
|              |              |
|       +------v------+       |
|       |    ITEM1    |       |
+-------+ prev | next +-------+
        |    DATA1    |
        +-------------+

4) two items in the list

      +----------+
      |          |
      |          |
      |   +------v------+
      |   |    HEAD     |
   +------+ prev | next +----+
   |  |   |ITEM2   ITEM1|    |
   |  |   +-------------+    |
+----------------------------+
|  |  |          |
|  |  |   +------v------+
|  |  |   |    ITEM1    |
|  |  +---+ prev | next +----+
|  |  |   |    DATA1    |    |
|  |  |   +-------------+    |
|  +-------------------------+
|     |          |
|     |   +------v------+
|     |   |    ITEM2    |
+---------+ prev | next +----+
      |   |    DATA2    |    |
      |   +-------------+    |
      |                      |
      +----------------------+

In the lock less algorithm there is a guarantee only for next pointer to be consistent. The guarantee wasn't always the case. The commit 2f073848c3cc introduces it.

Upvotes: 10

Related Questions