Unsafe Rust - how do I inform the compiler of side effects?

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've seen it. These are not intrusive lists as I need for my use case.

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.

If anyone's interested, here is the working playground.


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 ListElem IListElement 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 ().

1 Like

Thanks, that's good to know.

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.


Note that with allocators, however, the Allocator trait works with pointers to u8.


Allocators though need O(1) removal of interior blocks; a singly-linked list wouldn't be able to accomplish that.

Shall we start a new thread if there's enough interest?
The assignment to be replaced btw is CSApp3e's malloclab:



1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.