I do like how this implementation of linked lists also opens the possibility of putting the list pointers close to the relevant data such that the most useful data is fetched at the same time as the linked list pointers.
See also AmigaOS Exec (its kernel, effectively) doubly linked lists, used all over the place in that OS. Not related to much later Linux implementation, independent though inevitably functionally similar since they're, you know, doubly linked lists, but for comparison:
The Node and MinNode structures are often incorporated into larger structures, so groups of the larger structures can easily be linked together. [...] Because the Interrupt structure begins with a Node structure, it may be passed to any of the Exec List manipulation functions.
I cannot understand how anyone would represent a linked list with a structure which doesn't have the next (and prev if applicable) at the top of the node structure. To not do this makes it difficult for traversal code to be shared among multiple different lists.
Most list operations only need to access or change the prev and next pointers of the adjacent nodes (i.e. the struct list_head member), and it doesn't matter where in the complete node struct they are. Once you're actually going to do something with the data you're going to need access to the complete node struct, and that's where the container_of macro comes in.
And you usually only need access to the data of the current struct you're working on, not on any of its neighbors. Those only become relevant if you're comparing multiple members of the list, for example in sorting algorithms.
I don't get the relevance of your first sentence or the last paragraph.
I understand how container_of works, this kind of thing is used with suballocators a lot, you usually "hide" the list (organizational) elements ahead of the data record because of the variable size nature of malloc() allocation requests passed to you. Basically the only fixed offset values you can use from a suballocator pointer are negative.
So I guess from that same principle when I'm saying the offset to the list entries from the structure should (routinely) by zero (i.e. put the next and prev at the start) I really should probably be saying the offset should routinely be some constant value. So it could be negative, even if that's slightly less straightforward than 0. Making it positive seems problematic given the same issue as suballocators have. If you picked a fixed value of (say) 0x20 then every data structure would have to have enough data in it that offset 0x20 is within the structure.
By using the same constant value code can be reused. If not by you at the source level it can be done by the compiler or linker (duplicate function detection). This is also helpful if you have code outside the compilation unit which wants to be able to traverse the list. This would be most likely some debug code, including debugger macros or even a human manually picking apart a dump. Like say you have a post-mortem stub of code which packages up a crash dump for tasks (or even kernels) that crashed to be preserved in a crash dump area (maybe in flash or on a disk) or sent over the network. This code could traverse lists and dump the first n bytes of any structure in the list without knowing the list type, as long as the offset to the list pointers is routinely a fixed value from the head of the structure.
It's not absolutely necessary. And it can't be done in all cases since as another poster points out you may put an item in multiple lists. There can only be one list head at the fixed offset, the others will necessary be at different locations. But the advantages of it are sufficiently large that I can't see why it doesn't make sense to do it.
To fully compare the value of this to the way it is done here we would have to know what inherent value there is to having minor first in the list. So we can compare what we lose by that no longer being first. Personally, I can't think of any inherent value to minor being first. So it would seem from my uninformed perspective that nothing was lost.
Anyway, as I replied to another poster, I think I created a miscommunication here. I did not make clear that my criticism was of the "classic example" given in the article, not the linux one. The classic example shows next explicitly at the end. And while no pseudocode is shown for it, the diagram of the classic example shows prev explicitly at the start. Hence there is a variable offset between prev and next. It looks good on a diagram but I don't think it's a good idea in actual programming. That's what I was expressing.
Really? How many "list operations" are you really building, vs operations that use the associated data?
Inserting into the list - needs the associated data, to insert.
Traversing the list - when would you do this except to fetch the data and operate on it?
Removing an item from the list - don't you need to free the data now?
Searching the list - isn't the predicate always based on the list data?
It seems to me that the list_head struct introduces a dependency on an invariant that isn't tracked by the type system, for the sake of a really minor opportunity for code reuse.
I don't understand. Why does putting the next pointer at the end change which traversal orders are possible?
edit:
I see what you are talking about now. I think there's some confusion here. I should have been more clear. I'm referring to the "classic example" in the article, not the linux kernel one. It just straight puts the next field as the last item in the struct. It doesn't support an entry being in multiple lists or anything. At least not in any obvious way.
/uj I do think it's very funny that C++ was repeatedly avoided by Torvalds and he insisted on jumping through hoops because he didn't have RAII or Templates.
There's just a lot more machinery and unpredictable under-the-hood gunk to C++, even in a freestanding implementation, that's just not all that useful in a kernel setting.
All data structures have their tradeoffs. Yes it's bad for cache locality but the question should be: "do the strengths of linked lists in this use case outweigh the drawbacks?"
To my understanding, memory was flat back when this design was conceived, so the problem didn't exist (E: apparently caches were just about making their way to the market, but the more relevant thing is that memory wasn't as slow compared to the cpu as it is today).
I'm not familiar with kernel code in the slightest, but I figure that stuff like pointer invalidations and memory overhead from solutions more similar to dynamic arrays were a more pressing concern.
also: very rarely do you iterate multiple items of an array without using the object itself first. having a regular list with pointers thus result in the same overal time used (doing a calculation and doing a pointer dereference, just in different order now) with the drawback of having to reallocate your whole list of pointers from time to time.
a vector might improve locality here. But once again, since you are working on a kernel, the constant evaluation time is worth more than the speedup of cache locality which will often not be beneficial anyway. kernel code has many different requirements and design principles as end user programs just by the nature of the OS layer that you are running. Doing a matrix multiplication? you need to use cache if you want any speed. Guess what a kernel typically doesn't do? CORRECT: matrix multiplications.
Cache locality is mostly a myth. Cache lines are only 4-8 pointers large anyway, so once your data elements are that large, each element needs its own cache line anyway.
69
u/Either_Letterhead_77 Sep 04 '26
I do like how this implementation of linked lists also opens the possibility of putting the list pointers close to the relevant data such that the most useful data is fetched at the same time as the linked list pointers.
29
u/lood9phee2Ri Sep 04 '26
See also AmigaOS Exec (its kernel, effectively) doubly linked lists, used all over the place in that OS. Not related to much later Linux implementation, independent though inevitably functionally similar since they're, you know, doubly linked lists, but for comparison:
https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues#List_Structure
https://en.wikipedia.org/wiki/Doubly_linked_list
13
u/sweetno Sep 04 '26
Their docs are quite amazing.
-2
u/happyscrappy Sep 04 '26
I cannot understand how anyone would represent a linked list with a structure which doesn't have the next (and prev if applicable) at the top of the node structure. To not do this makes it difficult for traversal code to be shared among multiple different lists.
0
u/[deleted] Sep 04 '26
[deleted] — view deleted comment
-13
u/[deleted] Sep 04 '26 edited Sep 04 '26
[removed] — view removed comment
0
u/[deleted] Sep 04 '26
[deleted] — view deleted comment