10 ms·
Toward a better list iterator for the Linux kernel
- bitcharmer 5y agoDupe: https://news.ycombinator.com/item?id=30629914 https://news.ycombinator.com/item?id=30629914
- jwilk 5y agoIt has no comments, so there's no point linking to it.
- bitcharmer 5y agoThis one had no comments when I added mine.
- chmaynard 5y agolwn.net uses the term 'kernel' to refer to the Linux kernel. It's useful to add 'Linux' to the title for the benefit of HN readers.
- dddnzzz334 5y agoThat is because Linux Kernel is THE Kernel. There is no other Kernel that is relevant at all.
- chmaynard 5y agoWhat about Kernel Sanders?!
- dataflow 5y ago> 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 5y ago> 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.
- pjmlp 5y agoSomehow Arduino, Espressif, Google, Apple, Microsoft, IBM and ARM manage to do it.
- tialaramex 5y agoArduino, Espressif, Google, Apple, Microsoft, IBM and ARM all... have the same C++ subset in use which is widely agreed to be all the good bits? No? Maybe at least they've completely avoided political fights about the subset they're using, and all you'd find on that subject is an agreement that it's a matter of horses for courses, nobody is wrong? Also no? Well I'm sure that the Standard Committee's key people will write a document everybody agrees is a foundation for how to use modern C++, they could call it the "Core Guidelines"... Ah that didn't go well either did it. In fact as a C++ programmer you can probably even quote parts of the Core Guidelines you vehemently disagree with. It's a mistake to imagine that if Linus said "We'll use C++" that would end this nonsense, it would just make it even worse as of course people want to allow/reject their favourite/most hated features.
- pjmlp 5y agoThey agree on a specific internal one, just like Linux could agree in one specific one, yes? I am quite sure that when Rust happens to be lucky enough to have 40 years of history being deployed into production, we will also have our Rust Core Guidelines, yes? It is a mistake to imagine any language besides C would end the nonense arguments used by Linus.
- phkahler 5y agoI 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 5y agoNot sure I follow, can you explain with a code snippet?
- Akronymus 5y agoI think GP was referring to something like that https://www.youtube.com/watch?v=0ZEX_l0DFK0 https://www.youtube.com/watch?v=0ZEX_l0DFK0
- kevin_thibedeau 5y agoIf you need cheap double linking you should consider an XOR linked list.
- jmholla 5y agoWouldn't it need to be N-2? N-1's next is N, but prev should point to N-1.
- phkahler 5y agoThe only reason we need to point to N-1 is to get access to its next pointer for doing deletes (in my case where I never scan the list backwards). So rather than point to N-1 it suffices to point directly at its next pointer.
- 5y ago
- codys 5y agoFor more advanced intrusive lists in C, I've found that ccan's tlist2 (https://github.com/rustyrussell/ccan/blob/master/ccan/tlist2/tlist2.h 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 5y agoSeems pretty similar to FreeBSD's queue(3) (sys/queue.h). https://www.freebsd.org/cgi/man.cgi?query=queue&apropos=0&sektion=3 https://www.freebsd.org/cgi/man.cgi?query=queue&apropos=0&se... https://github.com/freebsd/freebsd-src/blob/main/sys/sys/queue.h https://github.com/freebsd/freebsd-src/blob/main/sys/sys/que...
- wahern 5y agoFor 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.
- codys 5y agoThe 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).
- bee_rider 5y agoThis 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.
- re 5y agoThis 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_external_storage https://en.wikipedia.org/wiki/Linked_list#Internal_and_exter...
- dottedmag 5y agoCache locality and memory consumption.
- loeg 5y ago> 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).
- Matthias247 5y agoNot only avoiding the cache miss. It's also avoiding an allocation. The non-intrusive list that the parent described means the list node requires one allocation, and the content another. Intrusive lists mean there's just one allocation required for the actual element - and hooking it into a list comes for free. If the struct we want to insert is on the stack we don't even need a single allocation. That is for example be useful on wait nodes, where we put some waiter object on the stack, register it in a shared wait queue, and then wait until the object gets signalled => No allocation is required for any waiter.
- jdlyga 5y ago"Toward a better list iterator for the Linux kernel" is a great name for a ship in the Halo universe
- bitwize 5y agoY'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.
- dbrueck 5y agoThe 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. :)
- pjmlp 5y agoArduino, Espressif, Google, Apple, Microsoft, IBM and ARM are perfectly confortable defining such C++ subset.
- stjohnswarts 5y agoHonestly 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...
- adgjlsfhk1 5y agogreat! they have selected a subset. It's called C.
- deleted 5y ago[deleted]
- notacoward 5y agoWorth noting that it's not just 15,000 uses in the Linux kernel. Many other projects, some of them quite large in their own right, have copied these macros. Obviously, changing the definitions used in the kernel won't affect those projects. However, many of the observations about safety and potential bugs do affect them as well.
- oconnor663 5y ago> 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 There's a lot of truth to this, but there's also more to the story: 1) Writing a doubly-linked list in safe Rust is famously difficult and cumbersome, yes. But writing a singly-linked list in safe Rust isn't so bad. Once you're familiar with Box and Option and how references work, you can make a singly-linked list out of those the way you'd expect. They're like unique_ptr<T> and optional<T> in C++. It's too much for a day-one exercise, which is part of why we often warn beginners away from it, but with some guidance it can definitely be a week-one exercise. 2) On the other hand, writing a singly- or doubly-linked list in unsafe Rust is hardly any different than writing it in C. That's the whole idea of unsafe Rust. You get your hands on some raw pointers and you go to town. Now, doing a good, idiomatic job of that means exposing a safe interface, and understanding the interactions between safe and unsafe Rust well enough to do that correctly takes a lot more experience. But getting an unsafe doubly-linked list to work in Rust as a proof of concept is arguably easy. It would be malpractice to teach it to beginners, but you could. [Edit: I was wrong about this. The simple version I was imagining failed Miri.] 3) As the article points out, "C lends itself to the creation of ad hoc linked lists in every situation where they are needed, resulting in boilerplate code and duplicated definitions." Rust does not lend itself to this, however, because like C++ it supports generic data structures. So even if implementing a linked list in Rust was the most difficult programming challenge the world had ever seen, that wouldn't be much of a problem in practice, because we could get some genius to implement it once, and then the rest of us could use it through a safe, generic API.
- anamax 5y ago> 1) Writing a doubly-linked list in safe Rust is famously difficult and cumbersome, yes. But writing a singly-linked list in safe Rust isn't so bad. Having never even seen a Rust program, let alone written one, if basic data structures are "famously difficult", ....
- oconnor663 5y agoI totally get what you mean. It is surprising. And because it's surprising, a lot of beginners dive right into it without realizing what they're getting into, and many wind up frustrated. It can feel like Rust is throwing up a bunch of pointless roadblocks at you for no reason. But here's how I'd summarize the reasoning behind it: In most languages, there are few or no restrictions on which objects are allowed to point to which other objects. In garbage collected languages (Java/Python/JS/Ruby/Go/etc), this is because the language runtime keeps objects alive for you as long as you hold pointers to them. In not-memory-safe native languages (C/C++/Zig/etc), this is because the language holds you responsible for avoiding use-after-free and other issues. These two groups of languages are quite different from each other, but one thing they have in common is that you'll never see an error message that says "Object A isn't allowed to point to object B." This is one of the things that makes Rust different from both of groups above. Rust is not garbage collected, but it is memory-safe. To make this work, the Rust compiler has strict rules around when you're allowed to retain a pointer to some object and when you're not. These rules have a substantial learning curve, partly because they can be tricky, but also because they're new and unfamiliar to most programmers. So the reason linked lists are more difficult to write in Rust is that they're pointer-heavy data structures. Implementing a linked list runs you straight into the pointer rules that make Rust different and sometimes tricky. To make everything work, you either need to spend some time studying those rules first, or you need a teacher who can point you in the right direction and answer your questions as you go. Anyway, if you're curious to learn more, there are several excellent books available, including an official one that we often just call The Book: https://doc.rust-lang.org/book/ https://doc.rust-lang.org/book/
- biryani_chicken 5y agoSome of the comments in the page mention Zig. While Zig has iterators for slices, the simple "for" loop (that actually uses the while keyword) makes you define the variable outside the loop: var i: usize = 0; while (i < 10): (i += 1) { //use i } I hope they fix this before 1.0.
- mariusor 5y agoI watched Jonathan Blow's introduction to macros in the Jai language[1] that he develops. Basically he made the for loop to be a macro (what he called a "hygienic macro") and it can be overloaded for various types of iterators. (watch past minute 6:30) [1] https://www.youtube.com/watch?v=QX46eLqq1ps https://www.youtube.com/watch?v=QX46eLqq1ps
- nyanpasu64 5y agoI don't use Zig but follow its development a bit. Zig has or may add foreach-like loops over one or more collections: https://github.com/ziglang/zig/issues/7257#issuecomment-1030588319 https://github.com/ziglang/zig/issues/7257#issuecomment-1030...
- Rygian 5y ago> It would be far nicer to have a single implementation that was known to work so that kernel developers could more profitably use their time introducing bugs into code that is truly unique to their problem area. Emphasis mine. That was a fun turn of phrase.