On 14.07.25 г. 11:14 ч., Nicolas Frattaroli wrote:
<snip>
+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 */
Nit: I think it's unnecessary to repeat the initilization in code since
you've already explicitly mentioned you continue form State 2 of the
previous example, so the only salient information is the additional
list_bulk_move_tail call.
+
+ 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.
The last part of the sentence can be simplified to just state the result
is undefined.
<snip>
+
+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);
nit: Might add a new line to make it more visually clear that you are
adding nodes to different lists.
+ 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:
---
base-commit: f55b3ca3cf1d1652c4b3481b671940461331d69f
change-id: 20250520-linked-list-docs-ce5b956d4602
Best regards,
One suggestion, how about adding O() complexity of the documented
functions.
