.. SPDX-License-Identifier: GPL-2.0+ =====================Linked Lists in Linux===================== :Author: Nicolas Frattaroli <nicolas.frattaroli@collabora.com> .. contents:: Introduction============ Linked lists are one of the most basic data structures used in many programs.The Linux kernel implements several different flavours of linked lists. Thepurpose of this document is not to explain linked lists in general, but to shownew kernel developers how to use the Linux kernel implementations of linkedlists. Please note that while linked lists certainly are ubiquitous, they are rarelythe best data structure to use in cases where a simple array doesn't alreadysuffice. In particular, due to their poor data locality, linked lists are a badchoice in situations where performance may be of consideration. Familiarizingoneself with other in-kernel generic data structures, especially for concurrentaccesses, is highly encouraged. Linux implementation of doubly linked lists=========================================== Linux's linked list implementations can be used by including the header file``<linux/list.h>``. The doubly-linked list will likely be the most familiar to many readers. It's alist that can efficiently be traversed forwards and backwards. The Linux kernel's doubly-linked list is circular in nature. This means that toget from the head node to the tail, we can just travel one edge backwards.Similarly, to get from the tail node to the head, we can simply travel forwards"beyond" the tail and arrive back at the head. Declaring a node---------------- A node in a doubly-linked list is declared by adding a struct list_headmember to the data structure you wish to be contained in the list: .. code-block:: c struct clown { unsigned long long shoe_size; const char *name; struct list_head node; /* the aforementioned member */ }; This may be an unfamiliar approach to some, as the classical explanation of alinked list is a list node data structure with pointers to the previous and nextlist node, as well the payload data. Linux chooses this approach because itallows for generic list modification code regardless of what data structure iscontained within the list. Since the struct list_head member is not a pointerbut part of the data structure proper, the container_of() pattern can be used bythe list implementation to access the payload data regardless of its type, whilestaying oblivious to what said type actually is. Declaring and initializing a list--------------------------------- A doubly-linked list can then be declared as just another struct list_head,and initialized with the LIST_HEAD_INIT() macro during initial assignment, orwith the INIT_LIST_HEAD() function later: .. code-block:: c struct clown_car { int tyre_pressure[4]; struct list_head clowns; /* Looks like a node! */ }; /* ... Somewhere later in our driver ... */ static int circus_init(struct circus_priv *circus) { struct clown_car other_car = { .tyre_pressure = {10, 12, 11, 9}, .clowns = LIST_HEAD_INIT(other_car.clowns) }; INIT_LIST_HEAD(&circus->car.clowns); return 0; } A further point of confusion to some may be that the list itself doesn't reallyhave its own type. The concept of the entire linked list and astruct list_head member that points to other entries in the list are one andthe same. Adding nodes to the list------------------------ Adding a node to the linked list is done through the list_add() macro. We'll return to our clown car example to illustrate how nodes get added to thelist: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { struct clown_car *car = &circus->car; struct clown *grock; struct clown *dimitri; /* State 1 */ grock = kzalloc_obj(*grock); if (!grock) return -ENOMEM; grock->name = "Grock"; grock->shoe_size = 1000; /* Note that we're adding the "node" member */ list_add(&grock->node, &car->clowns); /* State 2 */ dimitri = kzalloc_obj(*dimitri); if (!dimitri) return -ENOMEM; dimitri->name = "Dimitri"; dimitri->shoe_size = 50; list_add(&dimitri->node, &car->clowns); /* State 3 */ return 0; } In State 1, our list of clowns is still empty:: .------. v | .--------. | | clowns |--' '--------' This diagram shows the singular "clowns" node pointing at itself. In thisdiagram, and all following diagrams, only the forward edges are shown, to aid inclarity. In State 2, we've added Grock after the list head:: .--------------------. v | .--------. .-------. | | clowns |---->| Grock |--' '--------' '-------' This diagram shows the "clowns" node pointing at a new node labeled "Grock".The Grock node is pointing back at the "clowns" node. In State 3, we've added Dimitri after the list head, resulting in the following:: .------------------------------------. v | .--------. .---------. .-------. | | clowns |---->| Dimitri |---->| Grock |--' '--------' '---------' '-------' This diagram shows the "clowns" node pointing at a new node labeled "Dimitri",which then points at the node labeled "Grock". The "Grock" node still pointsback at the "clowns" node. If we wanted to have Dimitri inserted at the end of the list instead, we'd uselist_add_tail(). Our code would then look like this: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { /* ... */ list_add_tail(&dimitri->node, &car->clowns); /* State 3b */ return 0; } This results in the following list:: .------------------------------------. v | .--------. .-------. .---------. | | clowns |---->| Grock |---->| Dimitri |--' '--------' '-------' '---------' This diagram shows the "clowns" node pointing at the node labeled "Grock",which points at the new node labeled "Dimitri". The node labeled "Dimitri"points back at the "clowns" node. Traversing the list------------------- To iterate the list, we can loop through all nodes within the list withlist_for_each(). In our clown example, this results in the following somewhat awkward code: .. code-block:: c static unsigned long long circus_get_max_shoe_size(struct circus_priv *circus) { unsigned long long res = 0; struct clown *e; struct list_head *cur; list_for_each(cur, &circus->car.clowns) { e = list_entry(cur, struct clown, node); if (e->shoe_size > res) res = e->shoe_size; } return res; } The list_entry() macro internally uses the aforementioned container_of() toretrieve the data structure instance that ``node`` is a member of. Note how the additional list_entry() call is a little awkward here. It's onlythere because we're iterating through the ``node`` members, but we really wantto iterate through the payload, i.e. the ``struct clown`` that contains eachnode's struct list_head. For this reason, there is a second macro:list_for_each_entry() Using it would change our code to something like this: .. code-block:: c static unsigned long long circus_get_max_shoe_size(struct circus_priv *circus) { unsigned long long res = 0; struct clown *e; list_for_each_entry(e, &circus->car.clowns, node) { if (e->shoe_size > res) res = e->shoe_size; } return res; } This eliminates the need for the list_entry() step, and our loop cursor is nowof the type of our payload. The macro is given the member name that correspondsto the list's struct list_head within the clown data structure so that it canstill walk the list. Removing nodes from the list---------------------------- The list_del() function can be used to remove entries from the list. It not onlyremoves the given entry from the list, but poisons the entry's ``prev`` and``next`` pointers, so that unintended use of the entry after removal does notgo unnoticed. We can extend our previous example to remove one of the entries: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { /* ... */ list_add(&dimitri->node, &car->clowns); /* State 3 */ list_del(&dimitri->node); /* State 4 */ return 0; } The result of this would be this:: .--------------------. v | .--------. .-------. | .---------. | clowns |---->| Grock |--' | Dimitri | '--------' '-------' '---------' This diagram shows the "clowns" node pointing at the node labeled "Grock",which points back at the "clowns" node. Off to the side is a lone node labeled"Dimitri", which has no arrows pointing anywhere. Note how the Dimitri node does not point to itself; its pointers areintentionally set to a "poison" value that the list code refuses to traverse. If we wanted to reinitialize the removed node instead to make it point at itselfagain like an empty list head, we can use list_del_init() instead: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { /* ... */ list_add(&dimitri->node, &car->clowns); /* State 3 */ list_del_init(&dimitri->node); /* State 4b */ return 0; } This results in the deleted node pointing to itself again:: .--------------------. .-------. v | v | .--------. .-------. | .---------. | | clowns |---->| Grock |--' | Dimitri |--' '--------' '-------' '---------' This diagram shows the "clowns" node pointing at the node labeled "Grock",which points back at the "clowns" node. Off to the side is a lone node labeled"Dimitri", which points to itself. Traversing whilst removing nodes-------------------------------- Deleting entries while we're traversing the list will cause problems if we uselist_for_each() and list_for_each_entry(), as deleting the current entry wouldmodify the ``next`` pointer of it, which means the traversal can't properlyadvance to the next list entry. There is a solution to this however: list_for_each_safe() andlist_for_each_entry_safe(). These take an additional parameter of a pointer toa struct list_head to use as temporary storage for the next entry duringiteration, solving the issue. An example of how to use it: .. code-block:: c static void circus_eject_insufficient_clowns(struct circus_priv *circus) { struct clown *e; struct clown *n; /* temporary storage for safe iteration */ list_for_each_entry_safe(e, n, &circus->car.clowns, node) { if (e->shoe_size < 500) list_del(&e->node); } } Proper memory management (i.e. freeing the deleted node while making surenothing still references it) in this case is left as an exercise to the reader. Cutting a list-------------- There are two helper functions to cut lists with. Both take elements from thelist ``head``, and replace the contents of the list ``list``. The first such function is list_cut_position(). It removes all list entries from``head`` up to and including ``entry``, placing them in ``list`` instead. In this example, it's assumed we start with the following list:: .----------------------------------------------------------------. v | .--------. .-------. .---------. .-----. .---------. | | clowns |---->| Grock |---->| Dimitri |---->| Pic |---->| Alfredo |--' '--------' '-------' '---------' '-----' '---------' With the following code, every clown up to and including "Pic" is moved fromthe "clowns" list head to a separate struct list_head initialized at localstack variable ``retirement``: .. code-block:: c static void circus_retire_clowns(struct circus_priv *circus) { struct list_head retirement = LIST_HEAD_INIT(retirement); struct clown *grock, *dimitri, *pic, *alfredo; struct clown_car *car = &circus->car; /* ... clown initialization, list adding ... */ list_cut_position(&retirement, &car->clowns, &pic->node); /* State 1 */ } The resulting ``car->clowns`` list would be this:: .----------------------. v | .--------. .---------. | | clowns |---->| Alfredo |--' '--------' '---------' Meanwhile, the ``retirement`` list is transformed to the following:: .--------------------------------------------------. v | .------------. .-------. .---------. .-----. | | retirement |---->| Grock |---->| Dimitri |---->| Pic |--' '------------' '-------' '---------' '-----' The second function, list_cut_before(), is much the same, except it cuts beforethe ``entry`` node, i.e. it removes all list entries from ``head`` up to butexcluding ``entry``, placing them in ``list`` instead. This example assumes thesame initial starting list as the previous example: .. code-block:: c static void circus_retire_clowns(struct circus_priv *circus) { struct list_head retirement = LIST_HEAD_INIT(retirement); struct clown *grock, *dimitri, *pic, *alfredo; struct clown_car *car = &circus->car; /* ... clown initialization, list adding ... */ list_cut_before(&retirement, &car->clowns, &pic->node); /* State 1b */ } The resulting ``car->clowns`` list would be this:: .----------------------------------. v | .--------. .-----. .---------. | | clowns |---->| Pic |---->| Alfredo |--' '--------' '-----' '---------' Meanwhile, the ``retirement`` list is transformed to the following:: .--------------------------------------. v | .------------. .-------. .---------. | | retirement |---->| Grock |---->| Dimitri |--' '------------' '-------' '---------' It should be noted that both functions will destroy links to any existing nodesin the destination ``struct list_head *list``. Moving entries and partial lists-------------------------------- The list_move() and list_move_tail() functions can be used to move an entryfrom one list to another, to either the start or end respectively. In the following example, we'll assume we start with two lists ("clowns" and"sidewalk") in the following initial state "State 0":: .----------------------------------------------------------------. v | .--------. .-------. .---------. .-----. .---------. | | clowns |---->| Grock |---->| Dimitri |---->| Pic |---->| Alfredo |--' '--------' '-------' '---------' '-----' '---------' .-------------------. v | .----------. .-----. | | sidewalk |---->| Pio |--' '----------' '-----' We apply the following example code to the two lists: .. code-block:: c static void circus_clowns_exit_car(struct circus_priv *circus) { struct list_head sidewalk = LIST_HEAD_INIT(sidewalk); struct clown *grock, *dimitri, *pic, *alfredo, *pio; struct clown_car *car = &circus->car; /* ... clown initialization, list adding ... */ /* State 0 */ list_move(&pic->node, &sidewalk); /* State 1 */ list_move_tail(&dimitri->node, &sidewalk); /* State 2 */ } In State 1, we arrive at the following situation:: .-----------------------------------------------------.Lines 1–500 of 785. Load more
.. SPDX-License-Identifier: GPL-2.0+ ===================== Linked Lists in Linux ===================== :Author: Nicolas Frattaroli <nicolas.frattaroli@collabora.com> .. contents:: Introduction ============ Linked lists are one of the most basic data structures used in many programs. The Linux kernel implements several different flavours of linked lists. The purpose of this document is not to explain linked lists in general, but to show new kernel developers how to use the Linux kernel implementations of linked lists. Please note that while linked lists certainly are ubiquitous, they are rarely the best data structure to use in cases where a simple array doesn't already suffice. In particular, due to their poor data locality, linked lists are a bad choice in situations where performance may be of consideration. Familiarizing oneself with other in-kernel generic data structures, especially for concurrent accesses, is highly encouraged. Linux implementation of doubly linked lists =========================================== Linux's linked list implementations can be used by including the header file ``<linux/list.h>``. The doubly-linked list will likely be the most familiar to many readers. It's a list that can efficiently be traversed forwards and backwards. The Linux kernel's doubly-linked list is circular in nature. This means that to get from the head node to the tail, we can just travel one edge backwards. Similarly, to get from the tail node to the head, we can simply travel forwards "beyond" the tail and arrive back at the head. Declaring a node ---------------- A node in a doubly-linked list is declared by adding a struct list_head member to the data structure you wish to be contained in the list: .. code-block:: c struct clown { unsigned long long shoe_size; const char *name; struct list_head node; /* the aforementioned member */ }; This may be an unfamiliar approach to some, as the classical explanation of a linked list is a list node data structure with pointers to the previous and next list node, as well the payload data. Linux chooses this approach because it allows for generic list modification code regardless of what data structure is contained within the list. Since the struct list_head member is not a pointer but part of the data structure proper, the container_of() pattern can be used by the list implementation to access the payload data regardless of its type, while staying oblivious to what said type actually is. Declaring and initializing a list --------------------------------- A doubly-linked list can then be declared as just another struct list_head, and initialized with the LIST_HEAD_INIT() macro during initial assignment, or with the INIT_LIST_HEAD() function later: .. code-block:: c struct clown_car { int tyre_pressure[4]; struct list_head clowns; /* Looks like a node! */ }; /* ... Somewhere later in our driver ... */ static int circus_init(struct circus_priv *circus) { struct clown_car other_car = { .tyre_pressure = {10, 12, 11, 9}, .clowns = LIST_HEAD_INIT(other_car.clowns) }; INIT_LIST_HEAD(&circus->car.clowns); return 0; } A further point of confusion to some may be that the list itself doesn't really have its own type. The concept of the entire linked list and a struct list_head member that points to other entries in the list are one and the same. Adding nodes to the list ------------------------ Adding a node to the linked list is done through the list_add() macro. We'll return to our clown car example to illustrate how nodes get added to the list: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { struct clown_car *car = &circus->car; struct clown *grock; struct clown *dimitri; /* State 1 */ grock = kzalloc_obj(*grock); if (!grock) return -ENOMEM; grock->name = "Grock"; grock->shoe_size = 1000; /* Note that we're adding the "node" member */ list_add(&grock->node, &car->clowns); /* State 2 */ dimitri = kzalloc_obj(*dimitri); if (!dimitri) return -ENOMEM; dimitri->name = "Dimitri"; dimitri->shoe_size = 50; list_add(&dimitri->node, &car->clowns); /* State 3 */ return 0; } In State 1, our list of clowns is still empty:: .------. v | .--------. | | clowns |--' '--------' This diagram shows the singular "clowns" node pointing at itself. In this diagram, and all following diagrams, only the forward edges are shown, to aid in clarity. In State 2, we've added Grock after the list head:: .--------------------. v | .--------. .-------. | | clowns |---->| Grock |--' '--------' '-------' This diagram shows the "clowns" node pointing at a new node labeled "Grock". The Grock node is pointing back at the "clowns" node. In State 3, we've added Dimitri after the list head, resulting in the following:: .------------------------------------. v | .--------. .---------. .-------. | | clowns |---->| Dimitri |---->| Grock |--' '--------' '---------' '-------' This diagram shows the "clowns" node pointing at a new node labeled "Dimitri", which then points at the node labeled "Grock". The "Grock" node still points back at the "clowns" node. If we wanted to have Dimitri inserted at the end of the list instead, we'd use list_add_tail(). Our code would then look like this: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { /* ... */ list_add_tail(&dimitri->node, &car->clowns); /* State 3b */ return 0; } This results in the following list:: .------------------------------------. v | .--------. .-------. .---------. | | clowns |---->| Grock |---->| Dimitri |--' '--------' '-------' '---------' This diagram shows the "clowns" node pointing at the node labeled "Grock", which points at the new node labeled "Dimitri". The node labeled "Dimitri" points back at the "clowns" node. Traversing the list ------------------- To iterate the list, we can loop through all nodes within the list with list_for_each(). In our clown example, this results in the following somewhat awkward code: .. code-block:: c static unsigned long long circus_get_max_shoe_size(struct circus_priv *circus) { unsigned long long res = 0; struct clown *e; struct list_head *cur; list_for_each(cur, &circus->car.clowns) { e = list_entry(cur, struct clown, node); if (e->shoe_size > res) res = e->shoe_size; } return res; } The list_entry() macro internally uses the aforementioned container_of() to retrieve the data structure instance that ``node`` is a member of. Note how the additional list_entry() call is a little awkward here. It's only there because we're iterating through the ``node`` members, but we really want to iterate through the payload, i.e. the ``struct clown`` that contains each node's struct list_head. For this reason, there is a second macro: list_for_each_entry() Using it would change our code to something like this: .. code-block:: c static unsigned long long circus_get_max_shoe_size(struct circus_priv *circus) { unsigned long long res = 0; struct clown *e; list_for_each_entry(e, &circus->car.clowns, node) { if (e->shoe_size > res) res = e->shoe_size; } return res; } This eliminates the need for the list_entry() step, and our loop cursor is now of the type of our payload. The macro is given the member name that corresponds to the list's struct list_head within the clown data structure so that it can still walk the list. Removing nodes from the list ---------------------------- The list_del() function can be used to remove entries from the list. It not only removes the given entry from the list, but poisons the entry's ``prev`` and ``next`` pointers, so that unintended use of the entry after removal does not go unnoticed. We can extend our previous example to remove one of the entries: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { /* ... */ list_add(&dimitri->node, &car->clowns); /* State 3 */ list_del(&dimitri->node); /* State 4 */ return 0; } The result of this would be this:: .--------------------. v | .--------. .-------. | .---------. | clowns |---->| Grock |--' | Dimitri | '--------' '-------' '---------' This diagram shows the "clowns" node pointing at the node labeled "Grock", which points back at the "clowns" node. Off to the side is a lone node labeled "Dimitri", which has no arrows pointing anywhere. Note how the Dimitri node does not point to itself; its pointers are intentionally set to a "poison" value that the list code refuses to traverse. If we wanted to reinitialize the removed node instead to make it point at itself again like an empty list head, we can use list_del_init() instead: .. code-block:: c static int circus_fill_car(struct circus_priv *circus) { /* ... */ list_add(&dimitri->node, &car->clowns); /* State 3 */ list_del_init(&dimitri->node); /* State 4b */ return 0; } This results in the deleted node pointing to itself again:: .--------------------. .-------. v | v | .--------. .-------. | .---------. | | clowns |---->| Grock |--' | Dimitri |--' '--------' '-------' '---------' This diagram shows the "clowns" node pointing at the node labeled "Grock", which points back at the "clowns" node. Off to the side is a lone node labeled "Dimitri", which points to itself. Traversing whilst removing nodes -------------------------------- Deleting entries while we're traversing the list will cause problems if we use list_for_each() and list_for_each_entry(), as deleting the current entry would modify the ``next`` pointer of it, which means the traversal can't properly advance to the next list entry. There is a solution to this however: list_for_each_safe() and list_for_each_entry_safe(). These take an additional parameter of a pointer to a struct list_head to use as temporary storage for the next entry during iteration, solving the issue. An example of how to use it: .. code-block:: c static void circus_eject_insufficient_clowns(struct circus_priv *circus) { struct clown *e; struct clown *n; /* temporary storage for safe iteration */ list_for_each_entry_safe(e, n, &circus->car.clowns, node) { if (e->shoe_size < 500) list_del(&e->node); } } Proper memory management (i.e. freeing the deleted node while making sure nothing still references it) in this case is left as an exercise to the reader. Cutting a list -------------- There are two helper functions to cut lists with. Both take elements from the list ``head``, and replace the contents of the list ``list``. The first such function is list_cut_position(). It removes all list entries from ``head`` up to and including ``entry``, placing them in ``list`` instead. In this example, it's assumed we start with the following list:: .----------------------------------------------------------------. v | .--------. .-------. .---------. .-----. .---------. | | clowns |---->| Grock |---->| Dimitri |---->| Pic |---->| Alfredo |--' '--------' '-------' '---------' '-----' '---------' With the following code, every clown up to and including "Pic" is moved from the "clowns" list head to a separate struct list_head initialized at local stack variable ``retirement``: .. code-block:: c static void circus_retire_clowns(struct circus_priv *circus) { struct list_head retirement = LIST_HEAD_INIT(retirement); struct clown *grock, *dimitri, *pic, *alfredo; struct clown_car *car = &circus->car; /* ... clown initialization, list adding ... */ list_cut_position(&retirement, &car->clowns, &pic->node); /* State 1 */ } The resulting ``car->clowns`` list would be this:: .----------------------. v | .--------. .---------. | | clowns |---->| Alfredo |--' '--------' '---------' Meanwhile, the ``retirement`` list is transformed to the following:: .--------------------------------------------------. v | .------------. .-------. .---------. .-----. | | retirement |---->| Grock |---->| Dimitri |---->| Pic |--' '------------' '-------' '---------' '-----' The second function, list_cut_before(), is much the same, except it cuts before the ``entry`` node, i.e. it removes all list entries from ``head`` up to but excluding ``entry``, placing them in ``list`` instead. This example assumes the same initial starting list as the previous example: .. code-block:: c static void circus_retire_clowns(struct circus_priv *circus) { struct list_head retirement = LIST_HEAD_INIT(retirement); struct clown *grock, *dimitri, *pic, *alfredo; struct clown_car *car = &circus->car; /* ... clown initialization, list adding ... */ list_cut_before(&retirement, &car->clowns, &pic->node); /* State 1b */ } The resulting ``car->clowns`` list would be this:: .----------------------------------. v | .--------. .-----. .---------. | | clowns |---->| Pic |---->| Alfredo |--' '--------' '-----' '---------' Meanwhile, the ``retirement`` list is transformed to the following:: .--------------------------------------. v | .------------. .-------. .---------. | | retirement |---->| Grock |---->| Dimitri |--' '------------' '-------' '---------' It should be noted that both functions will destroy links to any existing nodes in the destination ``struct list_head *list``. Moving entries and partial lists -------------------------------- The list_move() and list_move_tail() functions can be used to move an entry from one list to another, to either the start or end respectively. In the following example, we'll assume we start with two lists ("clowns" and "sidewalk") in the following initial state "State 0":: .----------------------------------------------------------------. v | .--------. .-------. .---------. .-----. .---------. | | clowns |---->| Grock |---->| Dimitri |---->| Pic |---->| Alfredo |--' '--------' '-------' '---------' '-----' '---------' .-------------------. v | .----------. .-----. | | sidewalk |---->| Pio |--' '----------' '-----' We apply the following example code to the two lists: .. code-block:: c static void circus_clowns_exit_car(struct circus_priv *circus) { struct list_head sidewalk = LIST_HEAD_INIT(sidewalk); struct clown *grock, *dimitri, *pic, *alfredo, *pio; struct clown_car *car = &circus->car; /* ... clown initialization, list adding ... */ /* State 0 */ list_move(&pic->node, &sidewalk); /* State 1 */ list_move_tail(&dimitri->node, &sidewalk); /* State 2 */ } In State 1, we arrive at the following situation:: .-----------------------------------------------------.