Re: [PATCH v2] docs: document linked lists

[Nicolas Frattaroli <nicolas.frattaroli@collabora.com>]

On Monday, 7 July 2025 11:11:56 Central European Summer Time David Laight wrote:
> On Wed, 02 Jul 2025 22:24:47 +0200
> Nicolas Frattaroli <nicolas.frattaroli@collabora.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.

That is not what this is doing. In fact, the very first paragraph
of the documentation page that was too long for you to read does
explain this. What are you trying to achieve with this response?

> What may be relevant is a description of the types of linked list
> the kernel uses.

That is what this is.

> For that you pretty much only need a picture of the head and two
> items showing both the forward and backward pointers.

No you don't, that does not explain the operations on them. The way
the kernel embeds nodes as struct members to then do a container_of
on is not obvious to many, as is evidenced by there existing out-of-
tree documentation explaining this very fact. The way this interacts
with how these list operations are called is worth documenting.

> Then a list of the valid operations for that list type.

Function names are not self-explanatory. That lists are circular and
how that can break traversal after list modifications is not immediately
evident.

> What you can (efficiently) do with a list depends very much on how
> it is constructed.

No. O-notation was invented for a reason. There is no way in which you
can construct a list to make it not a linear search, even if you sort
it.

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

hlist literally just lacks a single pointer in the head, it does not
differ from the kernel's doubly linked list in any meaningful way,
and would be an actual TL;DR.

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

I don't see how your opinion on the datastructure is relevant here.

> 
> 	David
>