This is the back-link problem in Rust. You can do back links with weak pointers, but it's rather verbose and involves extra run-time checks.
I've been trying to figure out a compile-time approach to that problem.
Here's an early version of a tech note on that.[1]
It looks possible, but there are many issues. But it's important to look at now. The C++ people are trying to figure out safe backlinks.
It's pretty easy to do at runtime without weak pointers, people who write rust are just allergic to reference counting. Which is absurd, because most programmer use RC values thousands of times every day without even thinking about it. It's really this easy: https://pastebin.com/SAeKG7Sw
My gut says the following, so take with a grain of salt:
If your goal is to not do refcounting,
You can tie compile time guaranteed access on a 'parent getter' (but only ever as a non-mut reference) by saying:
- parent element MUST be present at time of construction
- When doing a 'parent get' call, you MUST still prove you're in the parent's lifetime.
This can be done at compile time at 0 runtime cost.
The problem is, that these constraints drastically reduce the usability of those back-links.
There is no compiler solution in Rust. Rust lifetimes form a DAG of (overlapping) ranges. (in terms that some leaf nodes are inductive proofs)
To relax those 2 constraints require a bi-directional graph, and I'm not sure if that can ever be computed in a reasonable time.
Insightful article. As they say doubly linked lists are approximately useless and never used. But trees were nodes can refer to their parents are extremely common.
And I agree, a custom arena is usually the best option here. Even though it seems like "giving up" and going back to C, it's still way better.
Some of them have keys that can't be reused too, so you can avoid "use after free" style bugs (at runtime) which is way better than C pointer wrangling.
It's not perfect though. I kind of wish Rust did have some kind of support for this stuff natively. Pretty low on my list of Rust desires though - way behind better compile time and fewer async footguns.
I'd like to see something powerful for safety and speed in Crates.io and Cargo:
The ability for crates to specify whether they use certain features of Rust:
- unsafe
- arena allocation or other future "useful" stuff
- proc_macros, eg. serde (a huge compile speed hit)
- deep transitive dependency (total #, or depth)
- some proxy for the "number of compiler steps" (compiler workload complexity)
We should be able to set a crate-wide or workspace-wide policy that can ban other crates that violate these rules.
We could make this hand-written early on, but eventually enforced by the compiler. You could then easily guarantee that no downstream dependency uses unsafe code, has a crazy number of dependencies, or has crazy compile times.
You could opt-in or opt-out to these things without having to think too much about them or constantly (manually) be on the lookout.
This would be hugely beneficial to the Rust ecosystem, safety, code quality, and developer productivity / happiness.
Perhaps what would be useful is crates.io determining through analysis which in the set of all lint(s) a crate is compatible with and exposing that as automatic metadata?
> Handles are deterministic. If a bug made your program crash on the last run, it will crash the same way on this run.
> Given that the arena will still be subject to array bounds checking, handle bugs won't allow an attacker to overwrite arbitrary memory the way pointer bugs do.
Just because you're in-bounds of the arena, doesn't mean you're not stomping on in-bounds neighboring data -- which can introduce "nondeterminism" as the author defines it. These are hand-waving arguments.
> doesn't mean you're not stomping on in-bounds neighboring data
I don't see how you would do that in safe rust though. The point of the arena would just be to solve the lifetime issue. It just moves the ownership problem one level higher. Instead of having circular ownership in a linked list, all linked list nodes are owned by the arena and hence have the same lifetime as the arena.
Here's an implementation of a doubly-linked list which is perfectly fine on modern hardware: an array of structs where each struct contains a pointer to its next and previous elements in addition to whatever other data is being stored.
Here's a situation where a traditional pointer-based double-linked list is fine: when the payload is very large (e.g., an entire document in some app).
> There are several ways to solve this problem. One way is to avoid using direct references to the particular class of objects at all. Instead, allocate a big array of objects, and refer to them with integer indexes into that array. There are several names that have been used for such arrays and indexes; let's call them arenas and handles.
I thought the term "Arena" referred to linear allocators, but maybe it's not so narrowly defined.
> At one level, this question is not very fair, because an answer to it as stated would be that one simply does not use doubly linked lists. They have been popular in introductory computer science lectures because they are a neat way to explain pointers in a data structure that's easy to draw on a whiteboard, but they are not a good match to modern hardware. The last time I used one was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
The arena data structure you described is inefficient unless it uses a linked list to track empty slots. All general-purpose heap allocators use linked lists in their implementations. Linked lists show up wherever you want pointer stability, low fragmentation, or a way to decouple the storage of objects from their participation in data structures. I struggle to imagine how it would be possible to implement something like Linux without at least one linked list in it.
> Essentially you are bypassing the notion of pointers provided directly by the hardware
Pointers aren't a hardware concept, they're a language concept. Array indices and pointers both rely on indirect addressing, which is the underlying hardware concept. The "handles" strategy in Rust feels like a kludgy approach not because it bypasses the hardware but because Rust's borrow checker isn't actually involved in ensuring safety in that case, just its bounds checking and mandatory initialization (and if all you need is those two things then...).
I'm a bit agnostic about the specific solution these days. In general, early binding(so, static memory and types, formalized arenas and handles, in-line linear logic with few or no loops or branches) debugs more readily than late(dynamic memory allocs and types, raw pointers, virtual functions, runtime configuration). The appeal of late binding is in deferring the final computation to later so that your options stay open, while the converse is true with early binding - if you can write a program that always returns a precomputed answer, that's easier to grasp and verify.
When we compare one method of early binding with another, it's probably going to be a comparison of the granularity. Arenas are "stupid simple" - they partition out memory into chunks that limit the blast radius of error, but you still make the error. Ownership logic is a "picky generalization" - it lets you be more intricate and gain some assurances if you put up with the procedures necessary, but it starts to inhibit certain uses because its view into usage is too narrow with too many corner cases.
If we take Go's philosophy as an example of "what do you do if you want idioms for a really scalable codebase" - though you can certainly argue that it didn't work - it's that you usually want to lean on the stupid simple stuff and customize what you need for the rest. You don't opt into a picky Swiss Army Knife unless there's a specific problem to solve with it. Larger codebases have proportionately smaller sections that demand intricacy because more and more of the code is going to itself be a method of defining late binding, of configuring and deferring parts of processing.
That said, Rust lets you fall back to "stupid simple", it just doesn't pave the way to make that the default.
> Doesn't that mean you are throwing out all the memory safety properties you were hoping to achieve by using Rust in the first place? ...That argument sounds logical, but it's not actually correct.
Actually, it is correct. The more generally you use "arenas" the more they are subject to the same kinds of issues as other manual memory management systems. "arenas" can only avoid/reduce the "nondeterminism" and "security" issues of general manual memory management on top of a buffer of bytes by not becoming general manual memory management on top of a buffer of bytes.
It all comes down to whether pointers into the arena do something different than normal pointers when they are dangling.
Normal pointers cause UB. That’s astronomically bad. If your arena pointers crash your program in a well-defined way, that’s already a much better situation.
I wish Rust would finalize its custom memory allocators api (allocator_api) and put it in the stdlib as soon as possible. That feature has been unstable for a decade now.
> The last time I used [a doubly linked list] was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
Curious to know in the Linux context whether moves away from doubly linked lists have ever been tested?
I kinda think rust is a dead-end. The learning curve is really challenging for most people, and you gain all these new constraints.
It competes against languages that give you memory safety by having garbage collection, or I guess even by using arenas in a few cases. GC comes with a performance hit, but a bit of a performance hit is usually much easier to deal with than having a smaller pool of effective developers
Given Rust’s memory safety goal, IMO the proper way to solve the circular reference problem in the context of Rust would be in the language. It should have a way to express what cycles may exist, maybe also how the code will break them when needed.
> The last time I used [a doubly linked list] was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
This and sibling comments about the supposed uselessness or outdatedness of linked lists taught me something about the disconnect between many systems engineers resistant to Rust and many members of the (evangelical) Rust community.
To address the technical topic first: a doubly linked list is what you reach for when you’re looking for an intrusive data structure with fast append and fast delete. You need to iterate over it, but don’t need random access. Queues where you may need to remove elements. Think a list of completions that can be cancelled.
Why an intrusive data structure? Because you don’t want to, or can’t allocate. Because you want only a non-owning reference to the object, and you don’t want to have to manage any other lifetimes or dynamic (potentially unbounded, or arbitrarily bounded) allocations. Intrusive data structures are a great tool to minimize allocations, and to keep allocations (and ownership) logically separated across modules.
And now onto the cultural topic. That a member of the Rust community might not know this (which is of course totally fine) is what taught me something, which was maybe obvious to many: Rust brings safety to a C++ style language and audience. For the same reasons many dislike C++, many dislike Rust. For the same reasons many would opt for C over C++ when they have the choice (either across all their projects or for certain projects), many continue to opt for C over Rust.
Rust will not be taking over systems programming for the same reasons C++ did not. Well, by the numbers, it probably did (and Rust probably will too), so maybe better to say that it will not stamp out C for systems programming for the same reasons C++ did not. And it’s not just because of the stubbornness of C programmers.
Systems programming has 2 cultures and practice groups: the C camp, and the C++ camp. The C++ camp is a big tent. I’d argue it includes Rust and Swift (and maybe D). Zig belongs to the C camp.
Safety is important, and maybe Rust has the right model for it, but it is not a solution for the C camp. It likely did not intend to be, and again, by the numbers, replacing C++ is probably the more important task.
The only Rust programs I've written are simple toys, and I don't know enough computer science to fully understand the problem space here. However, the first thing that comes to mind is, what if you just used unsafe for your doubly linked list?
I understand this defeats the point of using Rust. But if the argument is "I'm using C because I actually need doubly linked lists and Rust makes that hard/slow", well C is also unsafe, so using Rust with an unsafe block for your doubly linked list seems like an improvement.
I feel like at least part of the reason not to do this is "because the Rust community will yell at you." Well, maybe they shouldn't do that? If you were using C no one would care, so switching to unsafe Rust shouldn't imply the sky is falling.
The answer to "why not use unsafe" is it's hard to do correctly. What you have to do is pretty well documented https://doc.rust-lang.org/nomicon/working-with-unsafe.html but it's fiddly, tedious, easy to get wrong (you have to understand what the compiler is doing internally), and there are no automated checks to verify you have got it right. A newbie has almost no hope of getting right in the first 5 tries (5 is entirely made up.)
But, Rust already provides a linked list in it's standard library: https://doc.rust-lang.org/std/collections/struct.LinkedList.... So a Rust programmer might say there is no need use unsafe if you want a linked list. There is a "source" link on that page, so it isn't hard to see how it's done. Yes, it does use "unsafe".
Where it gets a little complex is a C programmer will look at that implementation and scoff at the linked list the Rust standard library provides. Amazingly the C and Rust programmers agree that this implementation is mostly useless. We know that because the Rust documentation says: "NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache [than this Rust linked list]."
When a C programmer uses a linked list, he almost invariably uses what someone above termed above an "intrusive" implementation. An intrusive implementation is typically faster, more memory efficient, and makes just as good use of the CPU cache as the Rust Vec or VecDeque. An intrusive implementation reserves a bit of memory inside of the object you want to put in a linked list for the linked list code. That memory is typically "owned" by the linked list code, as in it manages it's lifetime, whereas the lifetime of the object the memory is in is managed by some other mechanism. For example, if you delete some unrelated item it list, it might have to reach in and modify the linked list pointer in this item. But Rust has a simple memory model: if you modify an object you have to prove you own it. The linked list code reaching into another object can not do that.
That's one example, but intrusive linked lists break Rust's ownership and borrowing rules in so many ways, they are like oil and water. As far as I can tell there is no way to provide an intrusive linked list library in Rust that is safe to use, which is to say all code that uses it would have to be flagged as unsafe too.
This probably raises as more questions that it answered, and you are probably wondering how could two implementations of the same thing (a linked list) be so different. I'm not going to go down that rabbit hole, other than to remark it's clear a lot of Rust programmers commenting here don't understand the flexibility the intrusive method gives you. But their instincts are right about one thing: they are dangerous. It's the sort of danger a C programmer is entirely comfortable with, but that same danger is what has lead to C programmers being responsible for a of CVE's. They are right about another thing too: if you put a bit of thought into it, you can usually come up with something that is for all practical purposes just as fast, and the Rust compiler can prove is safe. Sometimes though, "a bit of thought" is an understatement, and sometimes it feels like you are in a straight jacket.
The article code be read is someone straining against that straight jacket, doing a lot of thinking and coming up with what a C programmer would call a fairly ugly (and slower) solution. The old C programmer in me says that's a fair summary. But I also have to acknowledge it is a very safe solution.
> As far as I can tell there is no way to provide an intrusive linked list library in Rust that is safe to use, which is to say all code that uses it would have to be flagged as unsafe too.
But if you need a linked list, would that be so bad? Again, the alternative is C where literally the whole program is unsafe...
> But if you need a linked list, would that be so bad?
The answer from a Rust programmers perspective is: yes, it's bad.
Rust's secret sauce is if you don't use unsafe, you have a memory safe language. In fact it's better than that. Due to its strong type system "safe Rust" is safer than almost all languages, including Java and the popular interpreted languages like Python, the one notable exception being Ada spark.
The problem with this rosy picture is unsafe Rust. It's harder to get right than C (which 100% unsafe), and you can't write a non-trivial Rust program without at least calling unsafe code. That means there is a trade-off going on. If Rust can keep the amount of unsafe code small and bounded, it wins over 100% unsafe C. If it can't, well you may as well use C.
Today's Rust does manage to keep unsafe code bounded. Just about any program can be written using purely safe code by using Rusts standard library ("std"). Std itself does contain a high'ish percentage of unsafe code (about 20%), but crucially a programmer using std never needs to use unsafe if they are prepared to make the occasional speed tradeoff (as could have been done in the article). Thus Rust + std + the rule "no unsafe", makes for a perfectly memory safe programming environment.
Based on that, a pact has now arisen in the Rust community. You are allowed to write libraries like "std" that use unsafe, but normal usage of those libraries must never require the caller to use unsafe code. The pact ensures unsafe code doesn't spread like a virus, and so Rust will always maintain it's safety advantage over C for your average programmer.
But, it's not possible to write an intrusive implementation of a linked list that doesn't required the caller to use unsafe. Therefore, any such library would be ostracised by the Rust community.
What I find is everything that I find interesting is cyclic, and so Rust has poor ergonomics for writing things I’m interested in. This is sad for me because it has the best compiler errors in the business. If I could get Swift with Rust’s compiler errors (Rust’s compiler in general is far better behaved) I’d be a happy chap.
30 comments
[ 2.6 ms ] story [ 65.2 ms ] threadLike if your arena contains both a buffer that OOB's and a buffer passed to a syscall, then having memory safety around the arena doesn't help you
I've been trying to figure out a compile-time approach to that problem. Here's an early version of a tech note on that.[1] It looks possible, but there are many issues. But it's important to look at now. The C++ people are trying to figure out safe backlinks.
[1] https://github.com/John-Nagle/technotes/blob/main/docs/rust/...
If your goal is to not do refcounting, You can tie compile time guaranteed access on a 'parent getter' (but only ever as a non-mut reference) by saying:
- parent element MUST be present at time of construction
- When doing a 'parent get' call, you MUST still prove you're in the parent's lifetime.
This can be done at compile time at 0 runtime cost. The problem is, that these constraints drastically reduce the usability of those back-links.
There is no compiler solution in Rust. Rust lifetimes form a DAG of (overlapping) ranges. (in terms that some leaf nodes are inductive proofs)
To relax those 2 constraints require a bi-directional graph, and I'm not sure if that can ever be computed in a reasonable time.
And I agree, a custom arena is usually the best option here. Even though it seems like "giving up" and going back to C, it's still way better.
There's this great comparison of Arenas in Rust: https://donsz.nl/blog/arenas/
Some of them have keys that can't be reused too, so you can avoid "use after free" style bugs (at runtime) which is way better than C pointer wrangling.
It's not perfect though. I kind of wish Rust did have some kind of support for this stuff natively. Pretty low on my list of Rust desires though - way behind better compile time and fewer async footguns.
The ability for crates to specify whether they use certain features of Rust:
- unsafe
- arena allocation or other future "useful" stuff
- proc_macros, eg. serde (a huge compile speed hit)
- deep transitive dependency (total #, or depth)
- some proxy for the "number of compiler steps" (compiler workload complexity)
We should be able to set a crate-wide or workspace-wide policy that can ban other crates that violate these rules.
We could make this hand-written early on, but eventually enforced by the compiler. You could then easily guarantee that no downstream dependency uses unsafe code, has a crazy number of dependencies, or has crazy compile times.
You could opt-in or opt-out to these things without having to think too much about them or constantly (manually) be on the lookout.
This would be hugely beneficial to the Rust ecosystem, safety, code quality, and developer productivity / happiness.
Perhaps what would be useful is crates.io determining through analysis which in the set of all lint(s) a crate is compatible with and exposing that as automatic metadata?
> Given that the arena will still be subject to array bounds checking, handle bugs won't allow an attacker to overwrite arbitrary memory the way pointer bugs do.
Just because you're in-bounds of the arena, doesn't mean you're not stomping on in-bounds neighboring data -- which can introduce "nondeterminism" as the author defines it. These are hand-waving arguments.
I don't see how you would do that in safe rust though. The point of the arena would just be to solve the lifetime issue. It just moves the ownership problem one level higher. Instead of having circular ownership in a linked list, all linked list nodes are owned by the arena and hence have the same lifetime as the arena.
Here's a situation where a traditional pointer-based double-linked list is fine: when the payload is very large (e.g., an entire document in some app).
I thought the term "Arena" referred to linear allocators, but maybe it's not so narrowly defined.
> At one level, this question is not very fair, because an answer to it as stated would be that one simply does not use doubly linked lists. They have been popular in introductory computer science lectures because they are a neat way to explain pointers in a data structure that's easy to draw on a whiteboard, but they are not a good match to modern hardware. The last time I used one was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
The arena data structure you described is inefficient unless it uses a linked list to track empty slots. All general-purpose heap allocators use linked lists in their implementations. Linked lists show up wherever you want pointer stability, low fragmentation, or a way to decouple the storage of objects from their participation in data structures. I struggle to imagine how it would be possible to implement something like Linux without at least one linked list in it.
> Essentially you are bypassing the notion of pointers provided directly by the hardware
Pointers aren't a hardware concept, they're a language concept. Array indices and pointers both rely on indirect addressing, which is the underlying hardware concept. The "handles" strategy in Rust feels like a kludgy approach not because it bypasses the hardware but because Rust's borrow checker isn't actually involved in ensuring safety in that case, just its bounds checking and mandatory initialization (and if all you need is those two things then...).
When we compare one method of early binding with another, it's probably going to be a comparison of the granularity. Arenas are "stupid simple" - they partition out memory into chunks that limit the blast radius of error, but you still make the error. Ownership logic is a "picky generalization" - it lets you be more intricate and gain some assurances if you put up with the procedures necessary, but it starts to inhibit certain uses because its view into usage is too narrow with too many corner cases.
If we take Go's philosophy as an example of "what do you do if you want idioms for a really scalable codebase" - though you can certainly argue that it didn't work - it's that you usually want to lean on the stupid simple stuff and customize what you need for the rest. You don't opt into a picky Swiss Army Knife unless there's a specific problem to solve with it. Larger codebases have proportionately smaller sections that demand intricacy because more and more of the code is going to itself be a method of defining late binding, of configuring and deferring parts of processing.
That said, Rust lets you fall back to "stupid simple", it just doesn't pave the way to make that the default.
Actually, it is correct. The more generally you use "arenas" the more they are subject to the same kinds of issues as other manual memory management systems. "arenas" can only avoid/reduce the "nondeterminism" and "security" issues of general manual memory management on top of a buffer of bytes by not becoming general manual memory management on top of a buffer of bytes.
Normal pointers cause UB. That’s astronomically bad. If your arena pointers crash your program in a well-defined way, that’s already a much better situation.
Curious to know in the Linux context whether moves away from doubly linked lists have ever been tested?
It competes against languages that give you memory safety by having garbage collection, or I guess even by using arenas in a few cases. GC comes with a performance hit, but a bit of a performance hit is usually much easier to deal with than having a smaller pool of effective developers
Worse is better
Have people been thinking about that?
This and sibling comments about the supposed uselessness or outdatedness of linked lists taught me something about the disconnect between many systems engineers resistant to Rust and many members of the (evangelical) Rust community.
To address the technical topic first: a doubly linked list is what you reach for when you’re looking for an intrusive data structure with fast append and fast delete. You need to iterate over it, but don’t need random access. Queues where you may need to remove elements. Think a list of completions that can be cancelled.
Why an intrusive data structure? Because you don’t want to, or can’t allocate. Because you want only a non-owning reference to the object, and you don’t want to have to manage any other lifetimes or dynamic (potentially unbounded, or arbitrarily bounded) allocations. Intrusive data structures are a great tool to minimize allocations, and to keep allocations (and ownership) logically separated across modules.
And now onto the cultural topic. That a member of the Rust community might not know this (which is of course totally fine) is what taught me something, which was maybe obvious to many: Rust brings safety to a C++ style language and audience. For the same reasons many dislike C++, many dislike Rust. For the same reasons many would opt for C over C++ when they have the choice (either across all their projects or for certain projects), many continue to opt for C over Rust.
Rust will not be taking over systems programming for the same reasons C++ did not. Well, by the numbers, it probably did (and Rust probably will too), so maybe better to say that it will not stamp out C for systems programming for the same reasons C++ did not. And it’s not just because of the stubbornness of C programmers.
Systems programming has 2 cultures and practice groups: the C camp, and the C++ camp. The C++ camp is a big tent. I’d argue it includes Rust and Swift (and maybe D). Zig belongs to the C camp.
Safety is important, and maybe Rust has the right model for it, but it is not a solution for the C camp. It likely did not intend to be, and again, by the numbers, replacing C++ is probably the more important task.
1. Implementing a linked list is a one and done deal and should be included in a (standard) library.
2. Would a classic pointer based implementation of a linked list in C really be a cause of security vulnerability??
I understand this defeats the point of using Rust. But if the argument is "I'm using C because I actually need doubly linked lists and Rust makes that hard/slow", well C is also unsafe, so using Rust with an unsafe block for your doubly linked list seems like an improvement.
I feel like at least part of the reason not to do this is "because the Rust community will yell at you." Well, maybe they shouldn't do that? If you were using C no one would care, so switching to unsafe Rust shouldn't imply the sky is falling.
But, Rust already provides a linked list in it's standard library: https://doc.rust-lang.org/std/collections/struct.LinkedList.... So a Rust programmer might say there is no need use unsafe if you want a linked list. There is a "source" link on that page, so it isn't hard to see how it's done. Yes, it does use "unsafe".
Where it gets a little complex is a C programmer will look at that implementation and scoff at the linked list the Rust standard library provides. Amazingly the C and Rust programmers agree that this implementation is mostly useless. We know that because the Rust documentation says: "NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache [than this Rust linked list]."
When a C programmer uses a linked list, he almost invariably uses what someone above termed above an "intrusive" implementation. An intrusive implementation is typically faster, more memory efficient, and makes just as good use of the CPU cache as the Rust Vec or VecDeque. An intrusive implementation reserves a bit of memory inside of the object you want to put in a linked list for the linked list code. That memory is typically "owned" by the linked list code, as in it manages it's lifetime, whereas the lifetime of the object the memory is in is managed by some other mechanism. For example, if you delete some unrelated item it list, it might have to reach in and modify the linked list pointer in this item. But Rust has a simple memory model: if you modify an object you have to prove you own it. The linked list code reaching into another object can not do that.
That's one example, but intrusive linked lists break Rust's ownership and borrowing rules in so many ways, they are like oil and water. As far as I can tell there is no way to provide an intrusive linked list library in Rust that is safe to use, which is to say all code that uses it would have to be flagged as unsafe too.
This probably raises as more questions that it answered, and you are probably wondering how could two implementations of the same thing (a linked list) be so different. I'm not going to go down that rabbit hole, other than to remark it's clear a lot of Rust programmers commenting here don't understand the flexibility the intrusive method gives you. But their instincts are right about one thing: they are dangerous. It's the sort of danger a C programmer is entirely comfortable with, but that same danger is what has lead to C programmers being responsible for a of CVE's. They are right about another thing too: if you put a bit of thought into it, you can usually come up with something that is for all practical purposes just as fast, and the Rust compiler can prove is safe. Sometimes though, "a bit of thought" is an understatement, and sometimes it feels like you are in a straight jacket.
The article code be read is someone straining against that straight jacket, doing a lot of thinking and coming up with what a C programmer would call a fairly ugly (and slower) solution. The old C programmer in me says that's a fair summary. But I also have to acknowledge it is a very safe solution.
> As far as I can tell there is no way to provide an intrusive linked list library in Rust that is safe to use, which is to say all code that uses it would have to be flagged as unsafe too.
But if you need a linked list, would that be so bad? Again, the alternative is C where literally the whole program is unsafe...
The answer from a Rust programmers perspective is: yes, it's bad.
Rust's secret sauce is if you don't use unsafe, you have a memory safe language. In fact it's better than that. Due to its strong type system "safe Rust" is safer than almost all languages, including Java and the popular interpreted languages like Python, the one notable exception being Ada spark.
The problem with this rosy picture is unsafe Rust. It's harder to get right than C (which 100% unsafe), and you can't write a non-trivial Rust program without at least calling unsafe code. That means there is a trade-off going on. If Rust can keep the amount of unsafe code small and bounded, it wins over 100% unsafe C. If it can't, well you may as well use C.
Today's Rust does manage to keep unsafe code bounded. Just about any program can be written using purely safe code by using Rusts standard library ("std"). Std itself does contain a high'ish percentage of unsafe code (about 20%), but crucially a programmer using std never needs to use unsafe if they are prepared to make the occasional speed tradeoff (as could have been done in the article). Thus Rust + std + the rule "no unsafe", makes for a perfectly memory safe programming environment.
Based on that, a pact has now arisen in the Rust community. You are allowed to write libraries like "std" that use unsafe, but normal usage of those libraries must never require the caller to use unsafe code. The pact ensures unsafe code doesn't spread like a virus, and so Rust will always maintain it's safety advantage over C for your average programmer.
But, it's not possible to write an intrusive implementation of a linked list that doesn't required the caller to use unsafe. Therefore, any such library would be ostracised by the Rust community.