How can I get myself out of this "mutable more than once" corner I've backed myself into?


#1

I have a library like stdlib’s MPSC called hopper. The difference with hopper is that it can buffer to disk if the in-memory storage gets too high: unbounded queued elements in bounded memory. The current stable – for reference – version functions but isn’t the fastest thing on the planet: senders and the receiver compete for a single mutex.

Lately I’ve been working to bust up this exclusive situation and move toward a system where all the senders synchronize on one end of a deque, the receiver synchronizes on the other. I feel like I’m really close to making this happen but I’ve worked myself into a corner and I’m kind of stuck. Hopefully someone here’ll see a way out I’ve missed. So, let me walk you through what I’ve got now. For reference, the commit I’m referencing is 34d40f575761332b2a5dcb76b027f334e5acf4f6.

Okay, the deque that’s lock protected on either end has an odd interface. For instance, enquing a T is push_back(&mut self, elem: T, mut guard: &mut MutexGuard<BackGuardInner<S>>) -> Result<bool, Error<T>>. There’s a lot going on here. elem: T is the thing we’re going to move into the deque. The bool that comes out in the Ok case of the return is a flag for if a stuck receiver needs to be notified – via a Condvar – that it’s free to start processing again. The elem: T is moved back to the caller in the case of error; more on that in a second. The implementation of push_back is fairly small, if, uh, pointerific:

pub unsafe fn push_back(
    &self,
    elem: T,
    guard: &mut MutexGuard<BackGuardInner<S>>,
) -> Result<bool, Error<T>> {
    let mut must_wake_dequeuers = false;
    if !(*self.data.offset((*guard).offset)).is_null() {
        return Err(Error::Full(elem));
    } else {
        *self.data.offset((*guard).offset) = Box::into_raw(Box::new(elem));
        (*guard).offset += 1;
        (*guard).offset %= self.capacity as isize;
        if self.size.fetch_add(1, Ordering::Release) == 0 {
            must_wake_dequeuers = true;
        };
    }
    return Ok(must_wake_dequeuers);
}

Why does a MutexGuard<BackGuardInner<S>> get passed as a reference to the function? Let’s take a look at a part of the main caller of push_back, hopper::Sender::send:

pub fn send(&mut self, event: T) {
    let mut back_guard = self.mem_buffer.lock_back();
    let placed_event = private::Placement::Memory(event);
    match self.mem_buffer.push_back(placed_event, &mut back_guard) {
        Ok(must_wake_receiver) => {
            if must_wake_receiver {
                let front_guard = self.mem_buffer.lock_front();
                self.mem_buffer.notify_not_empty(&front_guard);
                drop(front_guard);
            }
        }
        Err(deque::Error::Full(placed_event)) => {

Because hopper keeps memory bounded it’s possible that the send of an event will fail, signaling that we’re going to need to do something to get that event to disk. The approach taken is to pop the current back element off the in-memory buffer and fiddle with it based on it’s ‘placement’ status, which, uh, I guess is beside the point for this question but if you want to have a look dig in here or thereabouts. (This is not entirely reflected in-code. Just FYI.)

Anyhow, the trouble I’m in is that pushing and popping require a mutable deque as does getting the appropriate locks in the first place. The compiler is rightfully indignant:

error[E0499]: cannot borrow `self.mem_buffer` as mutable more than once at a time
   --> src/sender.rs:193:15
    |
191 |         let mut back_guard = self.mem_buffer.lock_back();
    |                              --------------- first mutable borrow occurs here
192 |         let placed_event = private::Placement::Memory(event);
193 |         match self.mem_buffer.push_back(placed_event, &mut back_guard) {
    |               ^^^^^^^^^^^^^^^ second mutable borrow occurs here
...
242 |     }
    |     - first borrow ends here

error[E0499]: cannot borrow `self.mem_buffer` as mutable more than once at a time
   --> src/sender.rs:196:39
    |
191 |         let mut back_guard = self.mem_buffer.lock_back();
    |                              --------------- first mutable borrow occurs here
...
196 |                     let front_guard = self.mem_buffer.lock_front();
    |                                       ^^^^^^^^^^^^^^^ second mutable borrow occurs here
...
242 |     }
    |     - first borrow ends here

error[E0499]: cannot borrow `self.mem_buffer` as mutable more than once at a time
   --> src/sender.rs:197:21
    |
191 |         let mut back_guard = self.mem_buffer.lock_back();
    |                              --------------- first mutable borrow occurs here
...
197 |                     self.mem_buffer.notify_not_empty(&front_guard);
    |                     ^^^^^^^^^^^^^^^ second mutable borrow occurs here
...
242 |     }
    |     - first borrow ends here

I considered moving the locks out of the deque entirely but the trouble I’ll have there is, well, how would I then implement Queue<T>::pop_front? This is the function that our condition variable makes an appearance in, the signaler of which is the sender sending. I also considered making the lock functions consume a closure where I’d do the meat of the function operation. But, I think this’ll run into problems too: back_lock has to be held for the duration of Sender::send, front_lock only for notifying the Receiver that more writes are ready. That’s a double mutation right there.

Anyhow, I’ve worked myself into a strong corner for sure. Anyone have an idea how I could work myself out of it?

TL;DR: I have a structure that holds mutexes to protect it and data functions on the same which take MutexGuards borrowed from the structure to mutate the structure. It’s a nasty loop that I’m not sure how to break.


Sqlite: caching prepared statements .... again
Sqlite: caching prepared statements .... again
#2

I didn’t look at the code in depth so I’ll just give a few high level suggestions for the “mutable more than once” class of issues:

  1. Instead of &mut self methods, mutably borrow individual fields. Since Rust understands field disjointness, this is usually an easier time. This may require moving state (fields) around the different structs to align them with the intended usage.
  2. Do more work in a single method, rather than calling different methods taking mutable borrows. In other words, manually inline the code (and/or use macros to help with that) into a function such that the cross-function boundary isn’t crossed, which is where borrowck “loses visibility” of what’s actually being borrowed.
  3. If you took out a lock on the structure, then continue doing mutable work through the lock guard itself (it derefs to the value inside) rather than a combination of the lock guard and mutable references.

See if this helps you. If not, I’ll try to digest the code some more when I have a bit more time.


#3

These are all excellent suggestions but I don’t see how to apply them straight off.

The trick here is that both Sender and Receiver are doing work through a mutable pointer: the deque data, *mut (*const T), is boxed in memory and each Queue<T> holds that as a *mut InnerQueue<T,S>.

pub struct Queue<T, S> {
    inner: *mut InnerQueue<T, S>,
}
struct InnerQueue<T, S> {
    capacity: usize,
    data: *mut (*const T),
    size: AtomicUsize,
    back_lock: Mutex<BackGuardInner<S>>,
    front_lock: Mutex<FrontGuardInner>,
    not_empty: Condvar,
}

There’s not individual fields so much as there’s one mutable place in memory that I need to coordinate access to. If Rust had a Mutex variant that were not pinned to scope I think this would be much more approachable with my current method; I need all the operations of Sender::send to be done only when the back_lock is held. So long as I use a Condvar to notify the Receiver that it’s got data to pull the Sender needs to have both a back_lock and the front_lock / Condvar pair that the Receiver has. The Receiver never interacts with back_lock.

Well, so that’s a thought I guess. I could see about pushing the code from the deque module up into their call sites: Sender / Receiver. This seems… drastic to me and I’d like to avoid that possibility if possible. Maybe it is the most sensible approach, given that I already have parameterized BackGuardInner<S> to allow the senders to coordinate through their back lock.

In this approach, the locks and condvar would migrate up into Sender / Receiver – I guess in Arcs – and there’d be a mutable pointer to the same stable-in-memory InnerQueue<T> but inside the Sender / Receiver pair. The *_back functions would migrate into Sender and the *_front functions would migrate into Receiver.

This is the approach that was used in hopper 0.3.0 and is what I’m migrating away from.


#4

Ok, I have another question after looking at the code snippets above. Why do lock_back, lock_front, notify_not_empty methods require &mut self rather than just &self? You’re already getting exclusivity by virtue of using the mutexes and the mutex guards you pass as parameter are sort of a “token” that the caller already has exclusive access to the data/operation they need. Maybe I’m missing something but that’s another high-level suggestion to look into: can you use &self borrows and rely on the fact you have mutexes and lock guards to enforce safety. The shared borrows of self would, of course, allow multiple of them at a time to exist.


#5

Oh hey, hmm, that’s an interesting idea. Let me run with that a bit.


#6

Okay, so I’ve made some progress and now have the mutable borrow issue worked back to where it’s only affecting Sender. Diff here: https://github.com/postmates/hopper/commit/0ad633391dc680cd6681ed971cc05452545ba81f

Particularly, the issue is with Sender::write_to_disk:

error[E0502]: cannot borrow `*self` as mutable because `self.mem_buffer` is also borrowed as immutable
   --> src/sender.rs:221:33
    |
183 |         let mut back_guard = self.mem_buffer.lock_back();
    |                              --------------- immutable borrow occurs here
...
221 |                                 self.write_to_disk(frnt, &mut back_guard);
    |                                 ^^^^ mutable borrow occurs here
...
258 |     }
    |     - immutable borrow ends here

write_to_disk is responsible for modifying self in the event of a disk queue file rollover. Of course, that doesn’t jive well with also taking a mutable borrow of a mutex out of self.

EDIT: I’m fairly certain I can rework the logic here to avoid needing to mutate self.


#7

So this is a good example of suggestion #1 and #2 I mentioned upthread: don’t mix holding mutable borrows of something from self and then calling methods that take &mut self - the compiler won’t know that you’re going to mutate something disjoint in that method (assuming you are).

Maybe you can inline write_to_disk or take a mutable borrow of a field it needs and then make it an associated function instead of a method - pass the required state as arguments.


#8

Just wanted to make sure to close the circle here and thank you for your help. I did manage to get all the mutable borrow issues resolved and have bundled up the work – plus related changes – in-repo. Boy I was stuck and you really did help!


#9

Glad you got it worked out. I’ve not looked at your repo link yet but what’s your take: do you think the structure that the borrow checker steered you towards makes the code better (eg more straightfoward data and control flow) in the process? Or do you think you had to contort it just to appease it?


#10

In retrospect the difficulty was not the borrow checker so much as it is that mutex is bound to scope. I worked my way out of the borrow checker bind I was in by pushing more data into the BackGuardInner, the inside of the back guarding mutex. In the end that’s fine – if maybe a little goofy at first sight – but what really twisted my code around was having to make sure the two MutexGuards always stay in-scope.

It’s a trade-off for safety, which I appreciate generally. Since hopper is already doing a lot of unsafe things I would not have minded an UnsafeMutex to use as well, one which is unbound from scope and has all the other sharp edges and what not I’d associate with a plain pthread mutex.

Minor thing, really. I’m not unhappy with how the code’s turned out. Just needed a fresh pair of eyes.


#11

Well, you could put a Mutex<()> next to an UnsafeCell…


#12

I backed myself into a similar corner with this code which was giving me:

error[E0499]: cannot borrow `self.root` as mutable more than once at a time
  --> src/main.rs:41:37
   |
41 |         self.put_key_into_node(&mut self.root, key, value)
   |         ----                        ^^^^^^^^^            - first borrow ends here
   |         |                           |
   |         |                           second mutable borrow occurs here
   |         first mutable borrow occurs here

error: aborting due to previous error

and managed to get myself out by refactoring some methods into standalone functions, to avoid simultaneously needing a mutable reference to “self” and “a field inside of self”.