Locking pairs of mutually referencing resources

Question

Consider the following:

// There are guys:
class Guy {
    // Each guy can have a buddy:
    Guy* buddy; // When a guy has a buddy, he is his buddy's buddy, i.e:
                // assert(!buddy || buddy->buddy == this);

public:
    // When guys are birthed into the world they have no buddy:
    Guy()
        : buddy{}
    {}

    // But guys can befriend each other:
    friend void befriend(Guy& a, Guy& b) {
        // Except themselves:
        assert(&a != &b);

        // Their old buddies (if any), lose their buddies:
        if (a.buddy) { a.buddy->buddy = {}; }
        if (b.buddy) { b.buddy->buddy = {}; }

        a.buddy = &b;
        b.buddy = &a;
    }

    // When a guy moves around, he keeps track of his buddy
    // and lets his buddy keep track of him:
    friend void swap(Guy& a, Guy& b) {
        std::swap(a.buddy, b.buddy);
        if (a.buddy) { a.buddy->buddy = &a; }
        if (b.buddy) { b.buddy->buddy = &b; }
    }
    Guy(Guy&& guy)
        : Guy()
    {
        swap(*this, guy);
    }
    Guy& operator=(Guy guy) {
        swap(*this, guy);
        return *this;
    }

    // When a Guy dies, his buddy loses his buddy.
    ~Guy() {
        if (buddy) { buddy->buddy = {}; }
    }
};

All is well so far, but now I want this to work when buddies are used in different threads. No problem, let's just stick std::mutex in Guy:

class Guy {
    std::mutex mutex;

    // same as above...
};

Now I just have to lock mutexes of both guys before linking or unlinking the pair of them.

This is where I am stumped. Here are failed attempts (using the destructor as an example):

1. Deadlock:

   ~Guy() {
       std::unique_lock<std::mutex> lock{mutex};
       if (buddy) {
           std::unique_lock<std::mutex> buddyLock{buddy->mutex};
           buddy->buddy = {};
       }
   }
   

   When two buddies are destroyed at around the same time, it is possible that each of them locks their own mutex, before trying to lock their buddies' mutexes, thus resulting in a deadlock.

2. Race condition:

   Okay so we just have to lock mutexes in consistent order, either manually or with std::lock:

   ~Guy() {
       std::unique_lock<std::mutex> lock{mutex, std::defer_lock};
       if (buddy) {
           std::unique_lock<std::mutex> buddyLock{buddy->mutex, std::defer_lock};
           std::lock(lock, buddyLock);
           buddy->buddy = {};
       }
   }
   

   Unfortunately, to get to buddy's mutex we have to access buddy which at this point is not protected by any lock and may be in the process of being modified from another thread, which is a race condition.

3. Not scalable:

   Correctness can be attained with a global mutex:

   static std::mutex mutex;
   ~Guy() {
       std::unique_lock<std::mutex> lock{mutex};
       if (buddy) { buddy->buddy = {}; }
   }
   

   But this is undesirable for performance and scalability reasons.

So is this possible to do without global lock? How?

Answer 1

Using std::lock isn't a race condition (per se) nor does it risk deadlock.

std::lock will use a deadlock-free algorithm to obtain the two locks. They will be some kind of (unspecified) try-and-retreat method.

An alternative is to determine an arbitrary lock order for example using the physical address of the objects.

You've correctly excluded the possibility that an objects buddy is itself so there's no risk of trying to lock() the same mutex twice.

I say isn't a race condition per se because what that code will do is ensure integrity that if a has buddy b then b has buddy a for all a and b.

The fact that one moment after befriending two objects they might be unfriended by another thread is presumably what you intend or addressed by other synchronization.

Note also that when you're befriending and may unfriend the friends of the new friends you need to lock ALL the objects at once. That is the two 'to be' friends and their current friends (if any). Consequently you need to lock 2,3 or 4 mutexes.

std::lock unfortunately doesn't take an array but there is a version that does that in boost or you need to address it by hand.

To clarify, I'm reading the examples of possible destructors as models. Synchronization on the same locks would be required in all the relevant members (e.g. befriend(), swap() and unfriend() if that is required). Indeed the issue of locking 2,3 or 4 applies to the befriend() member.

Furthermore the destructor is probably the worst example because as mentioned in a comment it's illogical that an object is destructible but may be in lock contention with another thread. Some synchronization surely needs to exist in the wider program to make that impossible at which point the lock in the destructor is redundant.

Indeed a design which ensures Guy objects have no buddy before destruction would seem like a good idea and a debug pre-condition that checks assert(buddy==nullptr) in the destructor. Sadly that can't be left as a run-time exception because throwing exceptions in destructors can cause program termination (std::terminate()).

In fact the real challenge (which may depend on the surrounding program) is how to unfriend when befriending. That would appear to require a try-retreat loop:

1. Lock a and b.
2. Find out if they have buddies.
3. If they're already buddies - you're done.
4. If they have other buddies, unlock a & b, and lock a and b and their buddies (if any).
5. Check that the buddies haven't changed, if they have go again.
6. Adjust the relevant members.

It's a question for the surrounding program whether that risks live-lock but any try-retreat method suffers the same risk.

What won't work is std::lock() a & b then std::lock() the buddies because that does risk deadlock.

So to answer the question - yes, it is possible without a global lock but that depends on the surrounding program. It may be in a population of many Guy objects contention is rare and liveness is high. But it may be that there are a small number of objects that are hotly contended (possibly in a large population) that results in a problem. That can't be assessed without understanding the wider application.

One way to resolve that would be lock escalation which in effect piecemeal falls back to a global lock. In essence that would mean if there were too many trips round the re-try loop a global semaphore would be set ordering all threads to go into global lock mode for a while. A while might be a number of actions or a period of time or until contention on the global lock subsides!

So the final answer is "yes it's absolutely possible unless it doesn't work in which case 'no'".