| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <0b85f378-221b-408e-865b-b4eab675a351@suse.com>
Date: Thu, 17 Jul 2025 13:27:30 +0300
From: Nikolay Borisov <nik.borisov@...e.com>
To: Nicolas Frattaroli <nicolas.frattaroli@...labora.com>,
Jonathan Corbet <corbet@....net>
Cc: Randy Dunlap <rdunlap@...radead.org>, kernel@...labora.com,
linux-doc@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] docs: document linked lists
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.
Powered by blists - more mailing lists