[HN Gopher] Toward a better list iterator for the Linux kernel
___________________________________________________________________
Toward a better list iterator for the Linux kernel
Author : chmaynard
Score : 52 points
Date : 2022-03-10 20:23 UTC (2 hours ago)
(HTM) web link (lwn.net)
(TXT) w3m dump (lwn.net)
| dataflow wrote:
| > One might argue that all of this is self-inflicted pain caused
| by the continued use of C in the kernel. That may be true, but
| better alternatives are in somewhat short supply. For example,
| since the Rust language, for all of its merits, does not make
| life easy for anybody wanting to implement a linked list, a
| switch to that language would not automatically solve the problem
|
| I feel like the elephant in the room is C++.
| Hermitian909 wrote:
| > I feel like the elephant in the room is C++.
|
| I don't think it's an elephant given how well trod the topic
| is. Linux maintainers want to avoid political fights about
| which subset of C++ the kernel uses, this is a struggle in
| large companies with top-down structures and would be a
| nightmare in something as collective as the kernel. Greg and
| Linus don't seem shy about occasionally saying "yes, it'd be
| nice if C has [C++ feature], oh well" but still want to
| maintain the current set of tradeoffs.
| jdlyga wrote:
| "Toward a better list iterator for the Linux kernel" is a great
| name for a ship in the Halo universe
| bitwize wrote:
| Or Banks's Culture novels. I bet _Towards a Better List
| Iterator for the Linux Kernel_ is great friends with _Smashing
| the Stack for Fun and Profit_.
| dbrueck wrote:
| Or a SpaceX drone ship!
| bitwize wrote:
| Y'know, these kinds of problems could have been avoided if Linus
| had simply... allowed C++ in the kernel. This may not be an "RMS
| not allowing GCC to expose the AST" tier instance of the BDFL
| obstructing a project's forward progress, but it's clear real
| damage has been done.
| tptacek wrote:
| There were strongly persuasive arguments against C++ when this
| was first litigated, and while those arguments have been
| blunted by C++'s progress in the ensuing time, at this point,
| if you're going to introduce a higher-level language to the
| kernel, it might as well be something with pro-forma memory
| safety, like Rust.
| google234123 wrote:
| Can there really be fair arguments when you have a culture of
| bullying?
| tptacek wrote:
| Yes. Also, I didn't use the word "fair".
| dbrueck wrote:
| The cost/benefit ratio would be way off though. The article
| mentions one of the proposals that Linus shot down "because it
| did nothing to prevent future problems from being introduced".
|
| Were they to use C++ in the kernel they'd have to first define
| which subset of C++ is allowed (in practice pretty much nobody
| uses all of C++ but instead uses some subset of it that they
| have more or less learned to use safely, and that subset varies
| wildly from person to person), and /then/ they'd have to add
| tooling to make sure nobody varies from that subset. :)
| stjohnswarts wrote:
| Honestly the core kernel programmers are extremely
| intelligent and I would trust their "subset" selection better
| than 99.999% of the other coders out there. Tamed of course
| with some input from graybeards like Stroustrup who I'm sure
| would be happy to interject his guidance ;) . I kind of wish
| Linus would relent...
| codys wrote:
| 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.
| loeg wrote:
| 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...
| wahern wrote:
| 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
| structure 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.
| bee_rider wrote:
| This is really part of the intro, but I wonder if someone knows
| anyway:
|
| My very naive first guess at making a generic linked list would
| be, of course, a struct with a 'next,' 'prev,' and the void
| pointer to the payload (What can I say? At some point my brain
| was damaged by OO languages). I guess their method of instead
| defining a struct, embedding the linked list into it, and then
| using macros would probably interact more nicely with the type
| system.
|
| Are there other benefits, though? I vaguely suspect their system
| might tend to prod users toward laying out their memory more
| nicely.
| dottedmag wrote:
| Cache locality and memory consumption.
| loeg wrote:
| > Are there other benefits, though?
|
| Yes; you're avoiding an extra pointer indirection between list
| navigation and element access, which is usually going to be a
| cache miss. Also if you have a pointer to an element of an
| intrusive list, you can cheaply navigate to the next element;
| this wouldn't work with your external list scheme (you'd need
| to maintain a separate list pointer instead).
| re wrote:
| This is called "internal" vs. "external" storage, or sometimes
| an "intrusive linked list". Fewer allocations and better
| locality of reference for faster access are some of the biggest
| benefits. There's more discussion here:
| https://en.wikipedia.org/wiki/Linked_list#Internal_and_exter...
| bitcharmer wrote:
| Dupe:
|
| https://news.ycombinator.com/item?id=30629914
| phkahler wrote:
| I had a need for doubly linked list and realized you can make the
| prev-> pointer point to a pointer_to_object rather than to an
| object (a pointer to a pointer). You point the prev pointer at
| the prior next-> pointer. In other words, the Nth objects prev
| pointer points at the (N-1)th objects next pointer. This was huge
| PITA but it allowed me to avoid putting an entire struct in the
| base object, just a single pointer initialized to NULL. So:
|
| BASE_OBJ->linked_obj1->linked_obj2->NULL
|
| Not showing the back links here, but BASE_OBJ only contains a
| pointer to linked_obj1 rather than an instance of its structure.
| You can add items to the list via that first pointer. Deletes
| work the same as usual too with the oddity of dealing with that
| *object.
| jjnoakes wrote:
| Not sure I follow, can you explain with a code snippet?
| kevin_thibedeau wrote:
| If you need cheap double linking you should consider an XOR
| linked list.
| jmholla wrote:
| Wouldn't it need to be N-2? N-1's next is N, but prev should
| point to N-1.
| dahfizz wrote:
| > Not showing the back links here, but BASE_OBJ only contains a
| pointer to linked_obj1 rather than an instance of its
| structure.
|
| I don't understand what you are after....
| struct Foo { struct Foo* prev; //Just a pointer, not
| an actual struct struct Foo* next; //Just a pointer,
| not an actual struct };
|
| That lets you "avoid putting an entire struct in the base
| object" without using a double pointer. It sounds like you did
| this: struct Foo { struct Foo** prev;
| //double pointer struct Foo* next; };
|
| Which works, but is strange...
___________________________________________________________________
(page generated 2022-03-10 23:00 UTC)