linux-kernel - Re: [PATCH v2] docs: document linked lists

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250707101156.2cc84294@pumpkin>
Date: Mon, 7 Jul 2025 10:11:56 +0100
From: David Laight <david.laight.linux@...il.com>
To: Nicolas Frattaroli <nicolas.frattaroli@...labora.com>
Cc: Jonathan Corbet <corbet@....net>, Randy Dunlap <rdunlap@...radead.org>,
 kernel@...labora.com, linux-doc@...r.kernel.org,
 linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2] docs: document linked lists

On Wed, 02 Jul 2025 22:24:47 +0200
Nicolas Frattaroli <nicolas.frattaroli@...labora.com> wrote:

> The kernel contains various generic data structures that should ideally
> not be reinvented. However, it often fails to document the usage of
> these in the in-tree kernel documentation beyond just a listing of
> header symbols in the very lengthy kernel-api docs page. This is fine
> for things that have simple invocations, but occasionally things devolve
> into several layers of concatenating macros, which are subpar for humans
> to parse.
> 
> Begin making a small impact by adding some rudimentary example-driven
> documentation for the linked list functions. Many aspects are covered,
> though it is not an exhaustive listing of the entire set of list
> operations. We also direct readers towards further documentation should
> they be interested in concurrency.
>

Jeepers; TLDR.
I don't think the kernel docs are a place to explain linked lists.
What may be relevant is a description of the types of linked list
the kernel uses.
For that you pretty much only need a picture of the head and two
items showing both the forward and backward pointers.
Then a list of the valid operations for that list type.
What you can (efficiently) do with a list depends very much on how
it is constructed.

Then repeat for hlist and hlist_nulls - I think they are the other
main list types.

IIRC 'LIST' is a double-linked list through a dummy item.
Not my favourite list type and can cause the sanitisers grief.

	David