Based on kernel version 6.17. Page generated on 2025-10-03 10:03 EST.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 |
.. 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(sizeof(*grock), GFP_KERNEL);
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(sizeof(*dimitri), GFP_KERNEL);
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::
.-----------------------------------------------------.
| |
v |
.--------. .-------. .---------. .---------. |
| clowns |---->| Grock |---->| Dimitri |---->| Alfredo |--'
'--------' '-------' '---------' '---------'
.-------------------------------.
v |
.----------. .-----. .-----. |
| sidewalk |---->| Pic |---->| Pio |--'
'----------' '-----' '-----'
In State 2, after we've moved Dimitri to the tail of sidewalk, the situation
changes as follows::
.-------------------------------------.
| |
v |
.--------. .-------. .---------. |
| clowns |---->| Grock |---->| Alfredo |--'
'--------' '-------' '---------'
.-----------------------------------------------.
v |
.----------. .-----. .-----. .---------. |
| sidewalk |---->| Pic |---->| Pio |---->| Dimitri |--'
'----------' '-----' '-----' '---------'
As long as the source and destination list head are part of the same list, we
can also efficiently bulk move a segment of the list to the tail end of the
list. We continue the previous example by adding a list_bulk_move_tail() after
State 2, moving Pic and Pio to the tail end of the sidewalk list.
.. 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 */
list_bulk_move_tail(&sidewalk, &pic->node, &pio->node);
/* State 3 */
}
For the sake of brevity, only the altered "sidewalk" list at State 3 is depicted
in the following diagram::
.-----------------------------------------------.
v |
.----------. .---------. .-----. .-----. |
| sidewalk |---->| Dimitri |---->| Pic |---->| Pio |--'
'----------' '---------' '-----' '-----'
Do note that list_bulk_move_tail() does not do any checking as to whether all
three supplied ``struct list_head *`` parameters really do belong to the same
list. If you use it outside the constraints the documentation gives, then the
result is a matter between you and the implementation.
Rotating entries
----------------
A common write operation on lists, especially when using them as queues, is
to rotate it. A list rotation means entries at the front are sent to the back.
For rotation, Linux provides us with two functions: list_rotate_left() and
list_rotate_to_front(). The former can be pictured like a bicycle chain, taking
the entry after the supplied ``struct list_head *`` and moving it to the tail,
which in essence means the entire list, due to its circular nature, rotates by
one position.
The latter, list_rotate_to_front(), takes the same concept one step further:
instead of advancing the list by one entry, it advances it *until* the specified
entry is the new front.
In the following example, our starting state, State 0, is the following::
.-----------------------------------------------------------------.
v |
.--------. .-------. .---------. .-----. .---------. .-----. |
| clowns |-->| Grock |-->| Dimitri |-->| Pic |-->| Alfredo |-->| Pio |-'
'--------' '-------' '---------' '-----' '---------' '-----'
The example code being used to demonstrate list rotations is the following:
.. code-block:: c
static void circus_clowns_rotate(struct circus_priv *circus)
{
struct clown *grock, *dimitri, *pic, *alfredo, *pio;
struct clown_car *car = &circus->car;
/* ... clown initialization, list adding ... */
/* State 0 */
list_rotate_left(&car->clowns);
/* State 1 */
list_rotate_to_front(&alfredo->node, &car->clowns);
/* State 2 */
}
In State 1, we arrive at the following situation::
.-----------------------------------------------------------------.
v |
.--------. .---------. .-----. .---------. .-----. .-------. |
| clowns |-->| Dimitri |-->| Pic |-->| Alfredo |-->| Pio |-->| Grock |-'
'--------' '---------' '-----' '---------' '-----' '-------'
Next, after the list_rotate_to_front() call, we arrive in the following
State 2::
.-----------------------------------------------------------------.
v |
.--------. .---------. .-----. .-------. .---------. .-----. |
| clowns |-->| Alfredo |-->| Pio |-->| Grock |-->| Dimitri |-->| Pic |-'
'--------' '---------' '-----' '-------' '---------' '-----'
As is hopefully evident from the diagrams, the entries in front of "Alfredo"
were cycled to the tail end of the list.
Swapping entries
----------------
Another common operation is that two entries need to be swapped with each other.
For this, Linux provides us with list_swap().
In the following example, we have a list with three entries, and swap two of
them. This is our starting state in "State 0"::
.-----------------------------------------.
v |
.--------. .-------. .---------. .-----. |
| clowns |-->| Grock |-->| Dimitri |-->| Pic |-'
'--------' '-------' '---------' '-----'
.. code-block:: c
static void circus_clowns_swap(struct circus_priv *circus)
{
struct clown *grock, *dimitri, *pic;
struct clown_car *car = &circus->car;
/* ... clown initialization, list adding ... */
/* State 0 */
list_swap(&dimitri->node, &pic->node);
/* State 1 */
}
The resulting list at State 1 is the following::
.-----------------------------------------.
v |
.--------. .-------. .-----. .---------. |
| clowns |-->| Grock |-->| Pic |-->| Dimitri |-'
'--------' '-------' '-----' '---------'
As is evident by comparing the diagrams, the "Pic" and "Dimitri" nodes have
traded places.
Splicing two lists together
---------------------------
Say we have two lists, in the following example one represented by a list head
we call "knie" and one we call "stey". In a hypothetical circus acquisition,
the two list of clowns should be spliced together. The following is our
situation in "State 0"::
.-----------------------------------------.
| |
v |
.------. .-------. .---------. .-----. |
| knie |-->| Grock |-->| Dimitri |-->| Pic |--'
'------' '-------' '---------' '-----'
.-----------------------------.
v |
.------. .---------. .-----. |
| stey |-->| Alfredo |-->| Pio |--'
'------' '---------' '-----'
The function to splice these two lists together is list_splice(). Our example
code is as follows:
.. code-block:: c
static void circus_clowns_splice(void)
{
struct clown *grock, *dimitri, *pic, *alfredo, *pio;
struct list_head knie = LIST_HEAD_INIT(knie);
struct list_head stey = LIST_HEAD_INIT(stey);
/* ... Clown allocation and initialization here ... */
list_add_tail(&grock->node, &knie);
list_add_tail(&dimitri->node, &knie);
list_add_tail(&pic->node, &knie);
list_add_tail(&alfredo->node, &stey);
list_add_tail(&pio->node, &stey);
/* State 0 */
list_splice(&stey, &dimitri->node);
/* State 1 */
}
The list_splice() call here adds all the entries in ``stey`` to the list
``dimitri``'s ``node`` list_head is in, after the ``node`` of ``dimitri``. A
somewhat surprising diagram of the resulting "State 1" follows::
.-----------------------------------------------------------------.
| |
v |
.------. .-------. .---------. .---------. .-----. .-----. |
| knie |-->| Grock |-->| Dimitri |-->| Alfredo |-->| Pio |-->| Pic |--'
'------' '-------' '---------' '---------' '-----' '-----'
^
.-------------------------------'
|
.------. |
| stey |--'
'------'
Traversing the ``stey`` list no longer results in correct behavior. A call of
list_for_each() on ``stey`` results in an infinite loop, as it never returns
back to the ``stey`` list head.
This is because list_splice() did not reinitialize the list_head it took
entries from, leaving its pointer pointing into what is now a different list.
If we want to avoid this situation, list_splice_init() can be used. It does the
same thing as list_splice(), except reinitalizes the donor list_head after the
transplant.
Concurrency considerations
--------------------------
Concurrent access and modification of a list needs to be protected with a lock
in most cases. Alternatively and preferably, one may use the RCU primitives for
lists in read-mostly use-cases, where read accesses to the list are common but
modifications to the list less so. See Documentation/RCU/listRCU.rst for more
details.
Further reading
---------------
* `How does the kernel implements Linked Lists? - KernelNewbies <https://kernelnewbies.org/FAQ/LinkedLists>`_
Full List API
=============
.. kernel-doc:: include/linux/list.h
:internal:
|