Cannot borrow mutable more than once error

help
1

Hi,

I am trying to understand why this fails.

        let mut cache = StringCache::new();
        let buf1 = String::from("hello").into_bytes();
        let result = cache.get(&buf1);
        let result2 = cache.get(&buf1);

I get:

error[E0499]: cannot borrow `cache` as mutable more than once at a time

However I don't see why this fails, as it is not being borrowed twice as far as I can see.

The signature of get is:

fn get(&'a mut self, buf: &'a std::vec::Vec<u8>) -> Option<&'a StringObject>

Regards

2

From section 5 of Common Rust Lifetime Misconceptions (if it compiles then my lifetime annotations are correct):

If we have some struct generic over 'a we almost never want to write a method with a &'a mut self receiver. What we're communicating to Rust is "this method will mutably borrow the struct for the entirety of the struct's lifetime" . In practice this means Rust's borrow checker will only allow at most one call to some_method before the struct becomes permanently mutably borrowed and thus unusable.

What you want instead is for get's mutable borrow to last for as long as the call itself. You might need something like:

fn get<'f>(&'f mut self, buf: &std::vec::Vec<u8>) -> Option<&'f StringObject>

But even that might be wrong. It's hard to tell what the proper lifetimes should be without seeing the code itself.

1 Like
3

If this is possible, it should work, as it ties the return value lifetime to the buf argument:

fn get<'b>(&mut self, buf: &'b std::vec::Vec<u8>) -> Option<&'b StringObject>

But I'm not sure that reflects what's actually implemented.

This would allow you to call cache.get more than once:

fn get(&mut self, buf: &std::vec::Vec<u8>) -> Option<&StringObject>

But the returned value will maintain exclusive the borrow of self until dropped. So you wouldn't be able to use the result of the first call after you made the second call.

4

As for why this error is occuring - when running the "no multiple mutable references" check, Rust doesn't care about whether it's an immutable reference or a mutable reference, if it came from (has the same lifetime) a mutable reference then it's treated as mutable.

1 Like
5

If you were allowed to use &mut cache while result still exists, then these rules would allow a program like this:

let result = cache.get(); // &mut borrowed
cache.clear();  // &mut borrowed more than once
println!("{}", result); // oops! Use-after-free

The borrow checker checks against method interfaces, not what the methods actually do, so fn get(&mut self) is treated as equally dangerous as fn destroy(&mut self).

For caches you're going to need to return Rc/Arc-wrapped objects. You could also use fn get(&self) and something like a memory pool/arena, or your own storage backed by unsafe, but you'd have to be super careful not to invalidate any references that were given out by your cache.

1 Like
6

I am still struggling to understand. Why does this work?

        let mut alloc = StringAllocator::new();
        let slice1 = alloc.alloc_string(10);
        let slice2 = alloc.alloc_string(10);

Signature of the function is:

fn alloc_string<'a>(&'a mut self, n: usize) -> Option<&'a mut [u8]>
7

Because you never use slice1, it's dropped before you create slice2. It's this situation:

To see this in action, try adding something like this:

    println!("{:?} {:?}", slice1, slice2);

That will force both attempted exclusive borrows to stick around, and you'll get a "cannot borrow alloc as mutable more than once at a time" error once more.

8

Well I wasn't using the values in the other example either.

Using both slice1 and slice2 does give an error - but the example that doesn't work doesn't try to use them both in this way.

9

The original example had a different problem. It had a method with this signature:

fn get(&'a mut self, buf: &'a std::vec::Vec<u8>) -> Option<&'a StringObject>

Note that the 'a lifetime here is not specific to the get method, so I assume this is a method on a type like StringCache<'a>. As ArifRoktim mentioned in the first reply above, borrowing a StringCache<'a> for the lifetime 'a forces it to remain borrowed for the rest of its life.

The solutions to this are discussed in the next comment. One of the solutions was to use an ellided lifetime for both self and the return type:

fn get(&mut self, buf: &std::vec::Vec<u8>) -> Option<&StringObject>

When we apply the lifetime elision rules, this expands to the following equivalent signature, which you can see is similar to the signature of alloc_string:

fn get<'b>(&'b mut self, buf: &std::vec::Vec<u8>) -> Option<&'b StringObject>
1 Like
10

Indeed you are correct that method is on StringCache<'a>.

I am trying to do this:

StringAllocator returns slices of u8 from a pool.
StringCache wants to create Boxed StringObjects that reference these slices. Boxed because StringObjects need to have a stable reference - so that I can use them without worrying about the references changing.

I am doing it this way to learn how to do the equivalent of what is in my C code. In the C version, StringObjects also come from an allocator - this is something I want to try next.

I should add that the aim is to cache all unique strings.

Regards

11

In Rust, worrying about references is typically the borrow cheker's job. You may be attempting something unsound, but it's hard to say without seeing the code (would it fit in the playground?).

If I'm understanding the goal, you may want to check out the Cow type.

12

The source is here:

https://github.com/ravilang/ravic/blob/main/lexer/src/lib.rs

Its my attempt to port from C code - deliberately want to do allocators etc from scratch to learn Rust.

Regards

13

Ah, I understand your comment about boxing and references now. While you have taken care to make the references stable across Vec reallocations in your allocator, the compiler can't really "see" this. The ownership and borrowing semantics are defined based on the function signatures. The upshot is that you can't modify your allocator while any other references are outstanding. Based on the function signature alone, the compiler can't tell that you're not invalidating any existing references.

It would be hard to safely work around this with the current approach even with runtime borrow checking, I feel, since you're returning a mutable subslice of one of your chunks. I.e. not even some sort of locking around your chunks is going to help.

15

I feel like you're trying to write something like bumpalo which however internally requires unsafe since there's no way you can prove to the compiler that you're not aliasing the slices you're giving out, nor that the previous slices will still be valid after adding a new one.

Another problem is that StringCache is a self-referential struct, also not possible in safe rust. You may try to use ouroboros to handle the necessary unsafe code.

16

Not sure I understood why you think StringCache is self referential.

17

It’s almost possible. If I were writing this, I’d probably approach it along these lines:

struct ChunkAllocator { /* ... */ }

impl ChunkAllocator {
    pub fn alloc(&self)->&mut [u8; CHUNK_SIZE] {
        // probably requires unsafe
    }
}

struct StringAllocator<'chunks> {
    alloc: &'chunks ChunkAllocator,
    chunks: Vec<Option<&'chunks mut [u8]>>
}

impl<'chunks> StringAllocator<'chunks> {
    pub fn alloc_string(&mut self, n:usize)->Option<&'chunks mut [u8]> {
        // To get a new chunk:
        self.chunks.push(Some(self.alloc.alloc()))

        // To take a piece of an existing chunk:
        let Some(chunk) = self.chunks[i].take();
        let (result, unused) = chunk.split_at_mut(n);
        self.chunks[i] = Some(unused);
    }
}
18

Well conceptually I can't see why I can't implement this.

I want to have a chunk allocator that returns references to slices - idea is that as long as the allocator lives, those chunks are valid.

Then I want to a string object allocator that returns structs that reference those slices. Again as long as this allocator has same or greater lifetime than the chunk allocator, it should work, right?

My problem is I am not sure how to express these lifetime relationships.

19

The string allocator needs to have a smaller lifetime than the chunk allocator, so that anything produced by the string allocator is guaranteed to be destroyed while the chunk allocator is still alive. That’s what my code snippet above does: the string allocator holds a reference to the chunk allocator, which means its existence will keep the chunk allocator alive.

The alloc_string method then returns references that are owned by the chunk allocator (and independent of the string allocator). That means the exclusive access implied by &mut self can end while the allocation is still mutably accessible.

The part that fundamentally requires unsafe is producing an &mut reference from an & reference: The compiler has no mechanism to verify that the exclusivity & non-aliasing constraints implied by the &mut are upheld.

Edit: It’s a little more subtle than that, actually: you can use something like Box::leak to safely generate a mutable reference to return from the allocator. What you can’t do safely is both return the &mut and keep a copy of it to access later for deallocation— That’s a prima facie violation of the borrowing rules that will require raw pointers or similar to implement.

1 Like
20

The StringObject<'a> in the map field borrows from the allocator field. You can see it clearer at lines 322-335. Another warning is that the get functions takes a &'a mut self, which is the same as &'a mut StringObject<'a>, which is (almost?) always wrong.

21

So I have been kind of stuck in my project where I am trying to port C code to Rust.

What appears to be very simple in C, seems impossible to do in Rust in the same way.

To recap:

My C project uses an allocator to dish out objects.
These objects are referred to in many other objects . I as a developer know that the lifetimes of these objects are all shorter than the allocator lifetime, so there is no problem with these memory references.
Additionally I need unique instances of objects - for example a string object only occurs once for a given string; I use Hash Sets to maintain unique sets of objects.

It seems that there is no way for me to implement this in Rust and convince the compiler that the code is safe ... that seems to be the gist of the feedback in this thread.

So I would like to implement following alternative.

I want to use regular Rust libraries and store each unique string in a Set. Then I would like to return an id that is not a reference to the object - but just an integer value. But I also need a way to map the id back to the object - so I am proposing to use a vector for that. In other words:

Given a string, find a unique String Object in the set that matches that string.
If not found, create a new String Object, store it in the set, assign it a unique id by appending it to a vector.
When presented the id, use the vector to map back to the object.

As far as I can tell since the object appears in two collections, I can use Rc to wrap it.

Is there a better way?

Regards

p.s. I could just use the reference counted object instead of an id I suppose. The id approach seems better in that it avoid having a fat reference everywhere.