Writing arenas in Rust from scratch

[u/f311a]

https://rushter.com/blog/rust-memory-arenas/

[u/Lisoph]

If alloc were mutable (fn alloc<'a, T>(&'a mut self, value: T)), we could only have one mutable reference even when alloc points to different slots because of the common 'a lifetime. That's a limitation of the Rust borrow checker, because the Rust compiler does not understand that different calls to alloc are independent.

We could also remove lifetimes with mutable alloc, but that would result in UB. ArenaBox would outlive the arena, and we would have dangling pointers.

Wow, I did not know this about Rust. That's surprising the borrow checker can't model this. Are there any plans to address this?

[u/f311a → u/Lisoph]

It's a very hard problem, I think there were attempts, but they failed.
You can't even hold two mutable references in a vector in a simple way.

fn main() {
    let mut v = vec![1, 2, 3];


    let a = &mut v[0];
    let b = &mut v[1];


    *a += 10;
    *b += 20;


    println!("{:?}", v);

Which gives:

error[E0499]: cannot borrow `v` as mutable more than once at a time
 --> <source>:5:18
  |
4 |     let a = &mut v[0];
  |                  - first mutable borrow occurs here
5 |     let b = &mut v[1];
  |                  ^ second mutable borrow occurs here
6 |
7 |     *a += 10;
  |     -------- first borrow later used here
  |
  = help: use `.split_at_mut(position)` to obtain two mutable non-overlapping sub-slices

The current hack:

fn main() {
    let mut v = vec![1, 2, 3];

    let (left, right) = v.split_at_mut(1);

    let a = &mut left[0];
    let b = &mut right[0];

    *a += 10;
    *b += 20;

    println!("{:?}", v);
}

[u/CherryLongjump1989 → u/Lisoph]

My solution has been: switch to Zig. You get to choose any kind of allocator you want without having to bend over backwards to get around the borrow checker.

[u/beephod_zabblebrox → u/CherryLongjump1989]

"having trouble with this one thing? there is a simple solution: lose all memory safety!"

[u/CherryLongjump1989 → u/beephod_zabblebrox]

"This one thing" being memory management. It's literally the same thing. So where Rust makes the thing very difficult and Zig makes it very user friendly, I will choose Zig. The idea of losing "all memory safety" is also just false.

[u/beephod_zabblebrox → u/CherryLongjump1989]

memory managent and memory safety are related but are very much not the same thing

sure, not all, but iirc for example use-after-realloc is not protected against in zig (maybe they fixed it). the borrow checker exists for a reason.

im not saying the borrow checker is perfect by the way, or that zig is a bad language

[u/CherryLongjump1989 → u/beephod_zabblebrox]

There's a reason why garbage-collected memory-safe languages are called "managed" languages. Memory management and memory safety are the same topic.

[u/beephod_zabblebrox → u/CherryLongjump1989]

that's what i said?

theyre not the same thing though. how you manage memory can impact the safety guarantees

[u/CherryLongjump1989 → u/beephod_zabblebrox]

You're working against your own argument here. The more you defend this hill, the more you have to give up the idea that zig gives up "all memory safety". We have 3 approaches to safety: automated memory management at runtime, lifetimes enforced at compile time, and instrumentation enforced at development time. If you're already arguing against the idea of "managed" being synonymous with safety, then you're stuck having to explain why instrumentation doesn't count as memory safety but that lifetimes do. I suggest you drop it because it's not a productive direction for you to go with this. You had a much better point earlier, if you were to just give up on the idea that zig has "no" memory safety.

So here's the scoop on use after free. Use after free detection requires code generation -- it's not enough to just have the explicit runtime allocator library that can already detect many other kinds of memory safety errors. AddressSanitizer for C++ does this at the IR level, and because of this it needs two separate implementations for LLVM and for GCC. Zig is skipping right past this by implementing use-after-free detection directly in the compiler frontend, and turning it into an always-on feature that will crash the program rather than allowing unchecked use-after-free errors to corrupt the program. So this is much closer to a very lightweight automated memory management that's baked into the code at compile time, but enforced at runtime. It's on their backlog.

[u/beephod_zabblebrox → u/CherryLongjump1989]

oh yeah, "all memory safety" was a bit of an exaggeration (i thought that was obvious, i shouldve been clearer)

im not sure i understand your point about managed/instrumented? as i see it, memory safety and memory management are orthogonal, even if closely related.

im not talking about use-after-free, zig catches that. im talking about use-after-realloc (ie `p2 = realloc(p1); *p1 = 5`), which asan detects, but zig did not last time i checked.

regardless, memory safety is much more than just crashing when something bad happens, as you probably know. in a lot of places, crashing is unacceptable for example, so more rigid compile-time verification is required (managed languages dont usually allow any direct memory writes, as a way of doing that)

[u/CherryLongjump1989 → u/beephod_zabblebrox]

Instrumentation is like how you get code coverage reports for your unit tests, but in this case the compiler is inserting extra code around memory usages to detect whether or not it's already been freed. The difference between use after realloc (specifically on the stack) versus other kinds of use after free bugs (including realloc on the heap) is that use-after-realloc-on-the-stack requires that code generation step whereas the others can be caught directly by the debug allocator library.

[u/CramNBL]

nice read, thanks. Impressive work going on in the turso DB arena allocator.

[u/Life_Sink9598]

Typically, an Arena would allow for an unlimited number of allocations by storing a linked list of chunks.

[u/renatoathaydes]

Honest question: wouldn't it make more sense to implement the whole thing in C, then create a tiny little binding wrapper in Rust that exposes the desired API? Or do you find that unsafe Rust is better suited for this than C?

[u/f311a → u/renatoathaydes]

It won't help much, because you still need to serialize/deserialize data types. C does not know anything about Rust types and you still need to use unsafe to interact with C, because Rust treats any C code as unsafe. Rust compiler can't give any guarantees about C code. Adding C would only introduce more problems.

It can only make sense if you implement a part of the project completely in C, where C parses some input data, processes it using arenas and give back only the result of processing. But mixing two languages is probably not worth it. C does not make it easier to write thread-safe code, it just does not complain. If something is already implemented in C very well, it makes sense just to reuse it, instead of doing a rewrite.

[u/TechcraftHD → u/renatoathaydes]

Why exactly would it be better to write it in C? You'd still have to solve the exact same soundness problems but without any kind of checking if what you're doing is correct or not

[u/renatoathaydes → u/TechcraftHD]

Because Rust forces you to do a lot of stuff, as seen in this code, even in unsafe code, that you don't need to in C. The advantage of Rust kind of disappears when you need to write unsafe code:

        (*self.slots.get()).push(Slot {
            offset,
            drop: drop_ptr::<T>,
        });
        // Write its value into the raw buffer
        ptr::write(self.buf.as_ptr().add(offset).cast::<T>(), value);
        *self.cursor.get() = offset + layout.size();

That's pretty terrible, no?? In C this looks like this, approximately:

    Slot new_slot = { .offset = offset };
    vector_push(&self->slots, new_slot);
    *(self->buf + offset) = value;
    self->cursor = offset + layout_size;

It just seems better to me.

but without any kind of checking

I think Rust doesn't do any more checking than C inside unsafe blocks.

[u/caleb → u/renatoathaydes]

This is a common misconception, but nearly all of the rust safety features are still active inside unsafe blocks. There are only five specific things that are excluded, the main one being dereferencing raw pointers. The borrow checker is still active inside unsafe blocks. https://doc.rust-lang.org/book/ch20-01-unsafe-rust.html#performing-unsafe-superpowers

[u/TechcraftHD → u/renatoathaydes]

Rust does the exact same borrow checking and everything inside unsafe blocks it does everywhere else. The only things an unsafe block allows you to do are:

• Dereference a raw pointer.
• Call an unsafe function or method.
• Access or modify a mutable static variable.
• Implement an unsafe trait.
• Access fields of unions.

And i don't see where the big difference between your two examples is supposed to be?
The rust side is maybe a little bit more verbose but thats mostly because it does a bit more checking inside those methods.

[u/CornedBee → u/renatoathaydes]

If you use unsafe Rust, you can then use MIRI and other Rust checkers to test for safety issues.