> 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.
Writing unsafe Rust is actually much harder than writing C or C++. C and C++ compilers apply certain optimizations quite conservatively (like anything involving aliasing) because the language doesn't assume a bunch of things like two mutable references never alias. Rust is a lot more aggressive.
If I was asked to rank them in terms of number of things you need to know to write fully correct (no UB) code, I would have: safe Rust < C++ < unsafe Rust
Ok I was going to try to be pedantic and say that if you could only use unsafe pointer operations, the aliasing issues don't apply. But the first example I tried to put together failed Miri, cause I was creating temporary &mut references to cast to *mut. So yeah...egg on face. Edited.
Rust (and, for that matter, C++ compilers) have always applied optimizations that rely on alias analysis. What I assume this thread is referring to is the noalias LLVM attribute on &mut function parameters. Rust now applies this.
Writing a doubly linked list is trivial if you use a backing vector and view into it. Which is how you should do it.
Linked lists are awful data structures and just as difficult to implement soundly in a thread safe context everywhere else. Rust just yells at you for doing it wrong.
I reiterate, unless you have a damn good reason, a linked list is an awful data structure. They're slow and cumbersome and have no advantages at small or large scales. The cases where you want them are few and far between and not in any undergraduate DSA course or application.
Yes, linked lists are overused in userspace, especially by beginners, but the "linked list bad" meme has gone too far. In particular, intrusive linked lists are commonly used in game engines and, oh yeah, operating system kernels for reasons ranging from memory efficiency to the ability to cheaply rearrange nodes.
> Linked lists are awful data structures and just as difficult to implement soundly in a thread safe context everywhere else. Rust just yells at you for doing it wrong.
This is a non-sequitur. Vectors and vector-based data structures are just as thread unsafe as basic linked lists. Furthermore, Rust isn't yelling at you for "doing it wrong". Safe Rust is yelling at you because the type system (by design) does not like cyclic ownership.
This is exactly the mindset that people hate about Rust, although I think it's unfair to associate it with the language because it's perpetuated by people who hold opinions like yours.
Linked lists are often not very performant on modern hardware. There's a lot of usecases where a vector (just as a generic collection or as the backing view) would be a better choice. Rust happens to make creating linked lists non-trivial. These are all facts.
The incorrect way to interpret this is how you've done: that linked lists are just wrong, and Rust happens to not let you use them because it wants you to not write wrong code so it makes this hard. Rust is a good language, but this is just a limitation of Rust, full stop. It's not some secret "the language authors are super smart and want you to stop writing linked lists". It's just that the language doesn't really let you do this, and it so happens that you can often get by with not creating them so Rust remains a productive language most of the time.
Linked lists remain incredibly useful in certain situations, of which an operating system kernel happens to be to feature a lot of. The ability to reliably allocate contiguous memory is not a given, and various thread safety and reference identity requirements make lists the only choice for a lot of parts of the kernel. This would be true regardless of the language you used to write it. Suggestions that linked lists are awful and have no advantages are quite frankly more of a sign of your limited experience with the environments where they would be useful than them being "wrong".
(Do note that I am not saying that the kernel only uses linked lists where appropriate: there's a lot of places where they're just a crutch to get around C being unable to deal with generic types without indirecting them behind a pointer, and Rust or even C++ would definitely be able to remove some of these "unfortunate" uses. But there's still plenty of linked lists that can not and will not be replaced regardless of the language the kernel is written in.)
Actually Rust lets you write linked lists of any kind very easily with reference counting. It's just that reference counting is no fun in C land. People like running around with loaded guns with disabled safety in their pocket.
Linked lists have a lot of pointers, that means a lot of things can go wrong. It's just that the mental strain of lots of things going wrong is too much for most humans so they just straight up ignore the safety aspects.
When you think about it, the ownership hierarchy of a linked list is quite complex. A lot of rust developers simply solve the problem by having a linked list container that owns all nodes. But in C land, it is pretty normal that the first node owns the second, the second owns the third, the third owns the fourth and so on. The ownership hierarchy is much more complicated, for not much benefit. Once you have a doubly linked list, ownership is no longer trivial because it cannot be expressed as a hierarchy.
Most languages have solved this with a garbage collector so it's really Rust that is the first language that is attempting a solution without a GC. In C land, the danger is part of the job, not something that anyone particularly cares about.
If your argument is "linked list memory management is rocket science so nobody should ever do it" then please stop. You're only digging yourself deeper.
No serious linked list implementation in Rust uses Rc<Refcell<_>>. They all use either unsafe or a vector of nodes because linked lists are among the most studied data structures in all of computer science and are extremely well-understood by skilled practitioners.
The people who wrote C and Pascal for decades didn't "straight up ignore the safety aspects." This is pure projection and only makes the Rust community (which I consider myself a part of) look bad.
An old presentation by Simon Peyton-Jones (of GHC fame) has a line like that: "Linked list implementation is first year programming course task; linked list implementation on multiprocessor is a PhD-level task; linked list implementation on multiprocessor using software transactional memory is again first year course task."
SPJ actually teaches students and oversees PhD students so these are not vain words.
STM greatly simplifies everything that is done in parallel, including, but not limited to, double linked lists.
Rust "yells at you doing it wrong" because Rust does not know any better way. Effects would help expressing safe STM computations, and they are just coming into Rust, hesitantly.
That reminds me of this article[1] by Bryan Cantrill. One takeaway is that Rust's ability to easily import generic data structures makes the average Rust program faster than the average C program.
With a bit of effort, C can be made faster than Rust, but if I'm writing a simple utility in C that needs a linked list, I'm going to write the simplest possible implementation, straight from an algorithms textbook. It's better for it to be slower, but more understandable and maintainable.
With Rust, the implementation I import has far more work put into it. I don't need to worry about how complex it is though, since its part of the standard library and I trust that people smarter than me have checked over what it does.
I 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/
I know why lists are hard to do with Rust's guarantees, and can even understand why a given memory safety validator might have trouble with them.
My point is that I expect a language eco-system to make it possible to do "easy" things without much trouble.
As the saying goes, a ship is safe in harbor, but that's not what ships are for.
Safety is a desirable property but it is not why (most of us) write programs. (I'm reminded of early Haskell, where programs could be guaranteed to produce the correct output but no guarantee that they'd produce output.)
There are only a few things in there that jump out to me as inconvenient:
- We have to write `unsafe` blocks in several places.
- When we dereference raw pointers, we have to write things like `(*self.head).next`, with more parentheses and stars than usual.
- We need to add PhantomData<T> members to our iterator types, so that the Rust compiler knows whether their lifetimes are covariant vs invariant.
None of those inconveniences adds very much in terms of lines of code. And of course, some of them are inconvenient by choice. Rust wants to be extra clear when we're doing unsafe things like dereferencing a raw pointer.
However, there are several places in this example where knowing the right thing to do is a serious challenge:
- The PhantomData<T> thing from above counts as one of these too, although a compiler message will point you to it if you forget.
- We need to store raw pointers to nodes rather than shared or mutable references to nodes.
- We allocate memory with Box::leak(Box::new(...)).
- We free memory with Box::from_raw(...) and end-of-scope destruction.
- We need to add an explicit Drop implementation to avoid leaking memory.
All of those are intermediate or advanced Rust concepts, and it doesn't make sense to try to teach them to beginners. It's also easy to get them wrong, much like malloc() and free() and constructors and destructors are easy to get wrong in C and C++. But once you understand these concepts and know how to use them, I wouldn't call them inconvenient per se. It's not clear to me that a helper library from the ecosystem would be able to help much here. Maybe we could find a way to reduce repitition in the implementations of the shared and mutable iterators? But for the most part, the challenge here is correctness, not repetition.
Oh yeah for sure. Even if you make sure your lists don't have any cycles, it's also possible for a given object to be on multiple different lists. Sometimes that's the whole point of the intrusive approach. But if you're accessible from multiple lists, there's no way a list can meet the uniqueness requirements of &mut. I guess you have two options:
1. Make the whole list API unsafe, so that the only way to expose a safe API on top of it is to make the list an internal implementation detail.
2. Take the Rc<RefCell<T>> or Arc<Mutex<T>> approach, where each element effectively has its own lock. Of course in high-performance code this is usually too expensive, and in any code calling .borrow() or .lock() all over the place is annoying.
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.
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.
`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.
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.
Nobody's mentioned what is IMO the main benefit of an intrusive data-structure: items within the data-structure can belong to multiple containers.
This allows you to locate an item using more than one criteria: for example, you could store blocks of free memory in two intrusive lists, one sorted by size and one by location. This would allow you to first locate eg. the largest memory block, and then quickly locate blocks adjacent to that one in memory.
With non-intrusive data-structures this is not possible, because while you can go from an iterator -> the item pointed to by the iterator, there is no way to efficiently do the reverse. This is possible in an intrusive data-structure because the iterator and the item itself are the same thing.
> So when you remove an element from the list, how do you make sure both lists are updated?
The remove_from_list() function has to be either payload-specific, or it needs a function pointer parameter which is called to handle the payload-specific unlinking. Assuming the lists are doubly-linked, which they typically are in the Linux kernel.
This is one of the purposes of doubly-linking the nodes.
Say your struct is in two lists. To remove it from both, first follow the next/prev pointers of the first list embedded struct to remove it from the first list, and then do the same thing with the second list embedded struct to remove it from the second list.
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...
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).
Not 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.
Yes. I would caution on inserting stack objects into shared lists, though, because it's such an easy footgun if the reference outlives the stack frame.
You could allocate a single novel struct containing
the structure of interest and any number of list elements that will contain it in a single malloc().
If the lists don’t need to know about each other, each novel struct could be different.
This would work, but it’s a bit exotic, so I’m not recommending it. But it addresses the locality and multiple allocation issues.
Not quite. With traditional intrusive linked lists, you'll have to modify the payload struct whenever you want to add it to another or different lists; with OP's approach, maybe not (but it depends on the implementation details).
> 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.
Some 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 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)
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.
The advantage is that, supposing the a pointer to the head of the list is stored in some other container, like
struct Container {
struct Foo *first_foo;
...probably more stuff...
};
then the first entry can have its `prev` field simply be `&container->first_foo`. (Each subsequent entry, as the OP said, has its `prev` field be `&previous_entry->next`.)
That way, you can have a function that removes an entry from the list, given only a pointer to the entry:
You get it exactly. I gave a more detailed explanation of the specific use-case in response to a sibling comment. It's one piece of a very complex data structure that does exactly what was needed efficiently - a dynamically updatable spatial index for geometric primitives.
Yes, that is exactly correct. Since you took the time, I'll offer a fuller explanation. It was for a spatial index where geometric objects were placed in an octtree. I also allowed each object to be inside more than one tree node for reasons (an objects position in the tree has nothing to do with other objects in the tree and I had to be able to straddle tree-node partitions).
This all lead to each octree node needing a list of things it contained, but I couldn't put the objects directly in the list because they needed to be contained by more than one node. Hence the linked list is actually made of:
struct Link {
struct Link** prev; //pointer to previous links next pointer (for delete)
struct Link* next; //Just a pointer, not an actual struct
struct Link* obj_next; //Pointer to the next link referencing this object
struct Treenode* node; //pointer to the containing tree node
struct Object* obj; //Pointer to an object in this tree node
};
You can start from an object and traverse a singly linked list of all the "Links" that reference it. This is used to delete an object. When querying the octree we come throught a doubly linked list using the first 2 pointers to find all object in the vicinity. That list is doubly linked to enable fast deletes of an object. The Link also contains a pointer to the tree node so after a deletion the node can be checked to see if it's empty (if so the tree is pruned). The Link obviously needs a pointer to the object since that's the entire goal - to find whats in the tree nodes.
I didn't want to include an instance of this whole structure within the tree nodes just to form a root for the list, so I modified the prev pointer into a pointer to a pointer which still allows quick deletes.
At some time I realized that 5 pointers isn't cache friendly so I XORed the pointers to the Treenode and the Object. Since we traverse these node starting from one of those 2 objects we can always recover the pointer to the other one is we store their XOR. This makes the links the size of 4 pointers at the expense of more ick, and did not impact performance at the time.
I'm not going to argue the merits of this approach to a spatial index, but I did find value in changing the prev pointer to a *ptr and that can be applied to any implementation.
The 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.
Worth 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.
> 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 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.
Arduino, 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.
They 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.
How do you figure? The C++ Core Guidelines date back to at least 2017, so 40 years before that would be 1977. At which point Stroustrup is still in Cambridge as a PhD student under Wheeler, he doesn't even travel to Bell Labs until after completing his Thesis.
Let's be honest here, the C++ Core Guidelines aren't because C++ is 20 or 30 or (if you squint very hard) 40 years old, they are a symptom of two things: 1. C++ programmers, including those on the Committee itself, don't agree about which dialect of C++ is good to use; 2: The ISO process is not well-suited to this work, even abused heavily it is a poor fit to the actual problem of standardizing a programming language under active development.
Rust avoids both these problems by choosing a more appropriate mechanism for decision making, one much more like that used at the IETF. The goal is to achieve consensus rather than getting one extra vote to put your favoured outcome over the line. The main casualties of a consensus approach are that "Marmite" proposals don't get far, however even if they survive the ballot process in a democracy they're likely to meet a terrible fate in the real world for the same reason - too many people hate them. On the other hand, mediocre proposals tend to get considerably improved during consensus making because there isn't any points scoring.
For example look at https://github.com/rust-lang/rust/pull/93208 -- The proposer initially wanted to offer Add<T> for Wrapping<T> but is it really clear this always does what the programmer expected? And if we're offering Add<T> for Wrapping<T> for symmetry we should also do Add<Wrapping<T>> for T right? So in the end the consensus is let's just offer AddAssign<T> because it's very clear in that case what's going on and it isn't symmetrical. And that's what will land in 1.60 next month.
Rust, the perfect language that still can't decide how to do asynchronous programming, has a endless collection of external crates for error propagation, yet has people that think they are the epitome of language design.
I will enjoy to see how perfection will be achieved in Rust ad eternum.
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.
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.
I am waiting to see the reasoning why creative uses of Rust macros or generics aren't problem in the Linux kernel versus Ada/C++ (yes there was an Ada based distribution on the early 2000's).
There are plenty of OSes using C++, at very least on kernel drivers.
I'd say it would be worth it for drivers, especially if someone comes up with a stable API so that there can be a competing Rust kernel that reuses the drivers.
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. :)
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...
This thread is literally about something that is a solved problem since 1991 in c++ (generic lists and data structures) and apparently still an issue in the kernel in 2022
And likewise Mozilla M-series builds supported DOM mangling 20+ years ago.
On paper that sounds like you could do much of what we do today, maybe with a little more effort but it'd work, right? Nope. In those M-series builds DOM mangling routinely crashed the browser. "Ask me how I know". And likewise your Borland C++ 3.0 "support" for templates means a lot of basic stuff works but if you try to get fancy (and of course there's no guidance provided on what's "fancy") you will get spurious errors or blow up the compiler, or worst of all, silently produce wrong binaries...
More than that though, having templates doesn't magically fix this problem. jcelerier says C++ fixes it by offering "generic lists" in 1991. But... it doesn't. In 1993-4 Stepanov presents the STL to the committee, with what will become std::list but that's not an intrusive list. So you would need to do all the heavy lifting to build your own intrusive lists, they are not, in fact, supplied with the language.
Thus we'd be in the exact same place, with people arguing about the implementation, except that (from experience) C++ proponents would be saying what the kernel needs is yet more C++ features...
You mean the same Mozilla that has killed Servo, layed off most Rust devs, keeps using C++ for the remaing part of Firefox, while trying to avoid fading into irrelevance, while Chrome and WebKit show no signs to ever move beyond C++, in spite of some exploratory work with Rust?
Or Rust existence depending on LLVM and GCC, both C++ projects, that will never adopt Rust as their main development language?
Better take care with the code generated by those C++ projects landing into the kernel as part of Rust runtime/stdlib.
Well in this case I'm talking about Mozilla the web browser, the initial product of Mozilla, years before Firefox. But yes, that's the right organisation.
Never is a very long time. Maybe safer to say they have no immediate intentions.
What is with the weird Nazi purity thinking when it comes to "code generated by those C++ projects" ? You know Linux is built with GCC today right?
Also - as I am pretty sure I explained to you before - Rust's standard libraries are arranged in a stack, the Rust for Linux project uses the ordinary core library (which implements a variety of useful stuff including core::iter::Iterator and core::option::Option) and provides its own alloc (a library for the allocator and the features that depend on it, such as alloc::boxed::Box but with explicit allocation and Error returns) however the rest of std is not supplied, Rust for Linux does supply kernel, which is full of kernel-specific stuff like kernel::random::getrandom
This is a much clearer division than is provided in the C++ Standard Library.
> So you would need to do all the heavy lifting to build your own intrusive lists, they are not, in fact, supplied with the language.
that's where we disagree I guess - the heaviest lifting you could do in C++, assuming zero standard library, is to me still orders of magnitude better, more readable and more maintainable than whatever can be done with macros in C.
No, because Linux has generic lists and data structures so you'd have to be more specific.
Also I was asking a particular person to because their perspective would have been interesting to me, but if you're also a kernel developer I would be interested to hear your gripes too.
I wonder if instead of assuming that the only "upgrade" from C is straight to C++ with all of its attendant baggage, may be what's needed is C with traits/templates and strict macros.
In other words, extend C in the same direction Rust took, but while retaining 100% backwards compatibility. Just adding traits and hygienic macros would make C much safer and ergonomic, while compiling down to normal C.
Basically what Arduino, Espressif, Google, Apple, Microsoft, IBM and ARM are perfectly confortable defining their C++ subsets for drivers and bare metal development.
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.