To provide a bit of background. I'm investigating whether Rust could replace C in the class I'm teaching. One of the assignments in this class is a memory allocator.
Commonly, an allocator's data structures are implemented using intrusive data structures such as intrusive linked lists or trees.
I'm pretty sure it is possible to do so in Rust since there's a crate out there that does it (intrusive_collections). This crate, however, is too high level for my purposes since it tries to provide a safe, or mostly safe, interface on top of intrusive lists whereas my use case by definition will not be safe (in other words, the borrowing rules etc. will not apply).
I was able to further diagnose the problem. As surmised, the issue stemmed from a violation of the aliasing rules for references. (I was able to verify this because the infinite loop disappeared when compiling with RUSTFLAGS="-Zmutable-noalias=no")
I've converted my code to not use Rust references at all, only raw pointers. It now works as expected.
Incidentally, the owner of that crate is a library team member and also wrote the current HashMap implementation. I'd expect that crate to be high quality and sound as well. Although it doesn't match your use case, it may be instructive to review the code.
This code still contains UBs. At least two of the points weren't resolved.
Also, you couldn't write UB-free linked list, so you expect your students to? If you can manage to work with singly linked lists, that's easier (even with intrusive).
If so, you cannot do it in Rust. Rust has strong safety guarantees, and code that aliases will never be valid.
It's possible that you can do without aliasing (for example, by storing pointers - still, you have to worry about aliasing, but only when dereferencing them). But if not (and I doubt this is really the case) - then Rust just cannot be used.
If you're referring to the ListElemIListElement casts, those are just for illustration. In the actual use case, it'll be casts between *mut u8 (where ) and *mut ListElement
The pinning part I'm trying to figure out. For a memory allocator, it'll be an issue only inasmuch as I'll like the compiler to catch potential sources of error.
Ultimately, whether Rust can be used for a memory allocator - and, in my opinion, more importantly, whether using Rust provides more robustness compared to a straight C implementation, is still up in the air, but I'm hopeful I will be able to use it (and at least partially benefit from some of its guarantees.) We did implement one in Rust when we followed Sergio's OS project, IIRC. (URL).
Note: the idiomatic "pointer to just about anything" in Rust is *mut (). One part of the reason behind that idiom is that actually taking a pointer to a zero-size type will typically give you a pointer to static storage (.rodata and friends), so if your code acts like the pointee of a *mut () is actually relevant, then it's not really pointing to something that was originally a ().
We will need to do some pointer arithmetic, though. When I take the example shown in the documentation and change it to * () like so it appears as though mem::size_of::<()>() is 0 (as opposed to GCC's sizeof(void) == 1 convention).
This seems feasible. I wouldn't start with a doubly linked list or copying structures from C. It might be better to work from the other direction, and start with the problem statement and see just how much can be done purely in safe Rust. It is certainly possible to write an intrusive singly linked list. It also may be worth taking a look at generational-arena. It's obviously not an allocator but its a similar structure and uses purely safe code.