Re: [PATCH v3] docs: document linked lists

[Nikolay Borisov]

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.