Hacker News Reader

Comment by codys | Hacker News Reader

For more advanced intrusive lists in C, I've found that ccan's tlist2 (https://github.com/rustyrussell/ccan/blob/master/ccan/tlist2...) provides a decent model here.

Compared to the linux kernel's intrusive lists, it also tracks the offset of the list_node within the structure contained by the list, which eliminates another class of problems. It does still have the "using the iterator after the for loop is over" issue discussed in this article, but it also already tracks the types as Linus proposed doing in the article to resolve the issue.

View on HN

Seems pretty similar to FreeBSD's queue(3) (sys/queue.h).

https://www.freebsd.org/cgi/man.cgi?query=queue&apropos=0&se...

https://github.com/freebsd/freebsd-src/blob/main/sys/sys/que...

For some reason the Linux community became enamored of the `container_of` construct, which eases typecasting across related structures, and built all their quasi-generic data structures around it. Whereas the traditional BSD implementations (substantially unchanged since 4.4BSD) never needed that bit of black magic; developers simply learned to avoid playing fast-and-loose with struct types in the first place.

In general the BSD implementations are more type-safe (just plain type-safe, actually), and IMO easier to use and much simpler to understand.

The difference appears to be:

`sys/queue.h` has it's pointers to the next element rather than the next list_node, while `ccan` and `linux` have pointers to the next list_node, which then are adjusted if needed to obtain the containing element.

In practice, this means that `sys/queue.h` is entirely macros, while linux & ccan's lists can use normal functions for most operations (with primarily obtaining the element pointer being handled by macros). Whether or not this is useful is somewhat dependent on compile time costs for macros vs code, and how small the list operations are in code size (ie: are they always inlined, or is it useful to be able to have a single instance of them). With the linux model, this can be determined at any time (by the compiler, or by the linked list library by changing it a bit), with the bsd model it is somewhat more difficult to make work (one could possibly do this by passing in the offset of the list_node structure to functions).

As proven by <sys/tree.h>, the same approach can still be used to generate functions, even external, shared functions as opposed to static routines duplicated in each compilation unit. OpenBSD's <sys/tree.h>, at least, can generate both.

But list operation are so short and simple there's no benefit (especially if using the BSD approach) to generating and invoking functions. It just adds complexity.

If I had to guess, and based on memory (I first learned C programming by reading Linux and GNU project code), things ended up the way they are because like many early C projects Linux took the road of writing subsystem-specific list implementations using C function interfaces. Over time these interfaces were incrementally unified and improved, the quasi-generic implementations made more type-safe using the container_of and related constructs.

<sys/queue.h> seems to have been the product of a seasoned kernel hacker who took the opportunities provided by the huge 4.4BSD refactor to create and push a single, unified approach to be used across the kernel.

To be clear, the linux approach doesn't need to "generate" functions: one can define the common operations as functions (and indeed, the linux kernel does this) that can be used for all list types.

The list operations themselves (iterating, adding list nodes, removing list nodes) are all type safe (and can be placed in normal functions), the piece that gets funky is only examining the element content (which uses `container_of`).

There's no reason to speculate on the origin of the the bsd and linux approaches here, and the speculation given is highly questionable.

Reply on news.ycombinator.com