When to Use Recursive Mutex

When to use recursive mutex?

For example when you have function that calls it recursively, and you want to get synchronized access to it:

void foo() {
   ... mutex_acquire();
   ... foo();
   ... mutex_release();
}

without a recursive mutex you would have to create an "entry point" function first, and this becomes cumbersome when you have a set of functions that are mutually recursive. Without recursive mutex:

void foo_entry() {
   mutex_acquire(); foo(); mutex_release(); }

void foo() { ... foo(); ... }

Is this an appropriate use case for a recursive mutex?

Both of your examples - the original synchronized_counter and the stack in your edit - are correct examples of using a recursive mutex, but they would be considered poor API design if you were building a data structure. I'll try to explain why.

Exposing internals - the caller is required to use the same lock that protects internal access to members of the data structure. This opens the possibility to misusing that lock for purposes other than accessing the data structure. That could lead to lock contention - or worse - deadlock.
Efficiency - it's often more efficient to implement a specialized bulk operations like increment_by(n) or pop_many(n).
- First, it allows the data structure to optimize the operations - perhaps the counter can just do count += n or the stack could remove n items from a linked list in one operation. [1]
- Second, you save time by not having to lock/unlock the mutex for every operation.[2]

Perhaps a better example for using a recursive mutex would be as follows:

I have a class with two methods Foo and Bar.
The class was designed to be single-threaded.
Sometimes Foo calls Bar.

I want to make the class thread-safe, so I add a mutex to the class and lock it inside Foo and Bar. Now I need to make sure that Bar can lock the mutex when called from Foo.

One way to solve this without a recursive mutex is to create a private unsynchronized_bar and have both Foo and Bar call it after locking the mutex.

This can get tricky if Foo is a virtual method that can be implemented by a sub-class and used to call Bar, or if Foo calls out to some other part of the program that can call back into Bar. However, if you have code inside critical sections (code protected by a mutex) calling into other arbitrary code, then the behaviour of the program will be hard to understand, and it is easy to cause deadlocks between different threads, even if you use a recursive mutex.

The best advice is to solve concurrency problems through good design rather than fancy synchronization primitives.

[1] There are some tricker patterns like "pop an item, look at it, decide if I pop another one", but those can be implemented by supplying a predicate to the bulk operation.

[2] Practically speaking locking a mutex you already own should be pretty cheap, but in your example it requires at least a call to an external library function, which cannot be inlined.

Recursive Lock (Mutex) vs Non-Recursive Lock (Mutex)

The difference between a recursive and non-recursive mutex has to do with ownership. In the case of a recursive mutex, the kernel has to keep track of the thread who actually obtained the mutex the first time around so that it can detect the difference between recursion vs. a different thread that should block instead. As another answer pointed out, there is a question of the additional overhead of this both in terms of memory to store this context and also the cycles required for maintaining it.

However, there are other considerations at play here too.

Because the recursive mutex has a sense of ownership, the thread that grabs the mutex must be the same thread that releases the mutex. In the case of non-recursive mutexes, there is no sense of ownership and any thread can usually release the mutex no matter which thread originally took the mutex. In many cases, this type of "mutex" is really more of a semaphore action, where you are not necessarily using the mutex as an exclusion device but use it as synchronization or signaling device between two or more threads.

Another property that comes with a sense of ownership in a mutex is the ability to support priority inheritance. Because the kernel can track the thread owning the mutex and also the identity of all the blocker(s), in a priority threaded system it becomes possible to escalate the priority of the thread that currently owns the mutex to the priority of the highest priority thread that is currently blocking on the mutex. This inheritance prevents the problem of priority inversion that can occur in such cases. (Note that not all systems support priority inheritance on such mutexes, but it is another feature that becomes possible via the notion of ownership).

If you refer to classic VxWorks RTOS kernel, they define three mechanisms:

mutex - supports recursion, and optionally priority inheritance. This mechanism is commonly used to protect critical sections of data in a coherent manner.
binary semaphore - no recursion, no inheritance, simple exclusion, taker and giver does not have to be same thread, broadcast release available. This mechanism can be used to protect critical sections, but is also particularly useful for coherent signalling or synchronization between threads.
counting semaphore - no recursion or inheritance, acts as a coherent resource counter from any desired initial count, threads only block where net count against the resource is zero.

Again, this varies somewhat by platform - especially what they call these things, but this should be representative of the concepts and various mechanisms at play.

std::mutex vs std::recursive_mutex as class member

Most of the time, if you think you need a recursive mutex then your design is wrong, so it definitely should not be the default.

For a class with a single mutex protecting the data members, then the mutex should be locked in all the public member functions, and all the private member functions should assume the mutex is already locked.

If a public member function needs to call another public member function, then split the second one in two: a private implementation function that does the work, and a public member function that just locks the mutex and calls the private one. The first member function can then also call the implementation function without having to worry about recursive locking.

e.g.

class X {
    std::mutex m;
    int data;
    int const max=50;

    void increment_data() {
        if (data >= max)
            throw std::runtime_error("too big");
        ++data;
    }
public:
    X():data(0){}
    int fetch_count() {
        std::lock_guard<std::mutex> guard(m);
        return data;
    }
    void increase_count() {
        std::lock_guard<std::mutex> guard(m);
        increment_data();
    } 
    int increase_count_and_return() {
        std::lock_guard<std::mutex> guard(m);
        increment_data();
        return data;
    } 
};

This is of course a trivial contrived example, but the increment_data function is shared between two public member functions, each of which locks the mutex. In single-threaded code, it could be inlined into increase_count, and increase_count_and_return could call that, but we can't do that in multithreaded code.

This is just an application of good design principles: the public member functions take responsibility for locking the mutex, and delegate the responsibility for doing the work to the private member function.

This has the benefit that the public member functions only have to deal with being called when the class is in a consistent state: the mutex is unlocked, and once it is locked then all invariants hold. If you call public member functions from each other then they have to handle the case that the mutex is already locked, and that the invariants don't necessarily hold.

It also means that things like condition variable waits will work: if you pass a lock on a recursive mutex to a condition variable then (a) you need to use std::condition_variable_any because std::condition_variable won't work, and (b) only one level of lock is released, so you may still hold the lock, and thus deadlock because the thread that would trigger the predicate and do the notify cannot acquire the lock.

I struggle to think of a scenario where a recursive mutex is required.

Recursive and Non-Recursive Locks (Mutex)

I think you'll be helped immensely by reading the wiki on Reentrant Mutexes. I would agree with the comments in that other thread; The accepted answer is wrong, or at least explains its point very, very poorly.

All Mutexes have a notion of ownership. That's what makes them different from a Semaphore. The thread that locks a mutex is always the thread that has to unlock it, and that's part of why mutexes can cause deadlock, but also why they work for their intended purpose (to mutually exclude access to a particular block of code).

So what is the difference between a Recursive/Reenrant and regular Mutex? A Recursive mutex can be locked multiple times by the same thread. To quote the wiki:

Recursive locks (also called recursive thread mutex) are those that allow a thread to recursively acquire the same lock that it is holding. Note that this behavior is different from a normal lock. In the normal case if a thread that is already holding a normal lock attempts to acquire the same lock again, then it will deadlock.

This is the entirety of the difference between the two mutex types. Essentially, you need a recursive mutex if you're placing a mutex lock inside a recursive method and the method recurses before the mutex is freed. Otherwise after the first recursion, there will be instant deadlock because the lock cannot be acquired a second time.

Really, this is the only reason to use a recursive mutex; Most other situations where you'd get the same thread trying to acquire the same lock without freeing it can probably be refactored into properly acquiring/freeing the lock without the need for a recursive mutex. And doing so will be much safer; A recursive function is naturally going to bubble out and free every lock on the recursive mutex assuming RAII, where as in other situations you may not sufficiently free the mutex and still wind up with deadlock.

So, to answer your specific questions:

No, unless your mutex system specifically allows this
Yes in both cases generally, though again this is mutex implementation specific with regards to blocking/throwing. Almost every system I've ever used just blocks (and that's why non-recursive mutexes deadlock if the same thread locks twice without a free)
Yes, usually, though generally they will be freed assuming proper RAII and the process terminates gracefully. Processes terminating non-gracefully while holding locks can be a bit of a crapshoot.
See my above explanations. Specifically, draw attention to the following from the wiki:

Note that the recursive lock is said to be released if and only if the number of times it has been acquired matches the number of times it has been released by the owner thread.

Why would we want to make a function recursive when it has a mutex lock?

In addition to paxdiablo's exmaple using an actual recursive funciotn, don't forget that using a mutex recursively doesn't necessarily mean that the functions involved are recursive. I've found use for recursive mutexes for dealing with a situation where you have complex operations which need to be atomic with respect to some data structure, with those complex operations rely on more fundamental operations that still need to use the mutex since the fundamental operations can be used on their own as well. An example might be something like the following (note that the code is illustrative only - it doesn't use proper error handling or transactional techniques that might really be necessary when dealing with accounts and logs):

struct account
{
    mutex mux;

    int balance;

    // other important stuff...

    FILE* transaction_log;
};

void write_timestamp( FILE*);

// "fundamental" operation to write to transaction log
void log_info( struct account* account, char* logmsg)
{
    mutex_acquire( &account->mux);

    write_timestamp( account->transaction_log);
    fputs( logmsg, account->transaction_log);

    mutex_release( &account->mux);
}

// "composed" operation that uses the fundamental operation.
//  This relies on the mutex being recursive
void update_balance( struct account* account, int amount)
{
    mutex_acquire( &account->mux);

    int new_balance = account->balance + amount;

    char msg[MAX_MSG_LEN];
    snprintf( msg, sizeof(msg), "update_balance: %d, %d, %d", account->balance, amount, new_balance);

    // the following call will acquire the mutex recursively
    log_info( account, msg);

    account->balance = new_balance;

    mutex_release( &account->mux);
}

To do something more or less equivalent without recursive mutexes means that the code would need to take care not to reacquire the mutex if it already held it. One option is to add some sort of flag (or thread ID) to the data structure to indicate if the mutex is already held. In this case, you're essentially implementing recursive mutexes - a trickier bit of work than it might seem at first to get right. An alternative is to pass a flag indicating you already acquired the mutex to functions as a parameter (easier to implement and get right) or simply have even more fundamental operations that assume the mutex is already acquired and call those from the higher level functions that take on the responsibility of acquiring the mutex:

// "fundamental" operation to write to transaction log
//  this version assumes that the lock is already held
static
void log_info_nolock( struct account* account, char* log msg)
{
    write_timestamp( account->transaction_log);
    fputs( logmsg, account->transaction_log);
}

// "public" version of the log_info() function that
//      acquires the  mutex
void log_info( struct account* account, char* logmsg)
{
    mutex_acquire( &account->mux);
    log_info_nolock( account, logmsg);    
    mutex_release( &account->mux);
}

// "composed operation that uses the fundamental operation
//      since this function acquires the mutex, it much call the
//      "nolock" version of the log_info() function
void update_balance( int amount)
{
    mutex_acquire( &account->mux);

    int new_balance = account->balance + amount;

    char msg[MAX_MSG_LEN];
    snprintf( msg, sizeof(msg), "update_balance: %d, %d, %d", account->balance, amount, new_balance);

    // the following call assumes the lock is already acquired
    log_info_nolock( account, msg);

    account->balance = new_balance;

    mutex_release( &account->mux);
}

How to use recursive QMutex

To create a recursive QMutex you simply pass QMutex::Recursive at construction time, for instance:

QMutex mutex(QMutex::Recursive);
int number = 6;

void method1()
{
    mutex.lock();
    number *= 5;
    mutex.unlock();
}

void method2()
{
    mutex.lock();
    number *= 3;
    mutex.unlock();
}

Recursive means that you can lock several times the mutex from the same thread, you don't have to unlock it. If I understood well your question that's what you want.

Be careful, if you lock recursively you must call unlock the same amount of times. A better way to lock/unlock a mutex is using a QMutexLocker

#include <QMutexLocker>

QMutex mutex(QMutex::Recursive);
int number = 6;

void method1()
{
    QMutexLocker locker(&mutex); // Here mutex is locked
    number *= 5;
    // Here locker goes out of scope.
    // When locker is destroyed automatically unlocks mutex
}

void method2()
{
    QMutexLocker locker(&mutex);
    number *= 3;
}

Recursive locking in Go

I'm sorry to not answer your question directly:

IMHO, the best way how to implement recursive locks in Go is to not implement them, but rather redesign your code to not need them in the first place. It's probable, I think, that the desire for them indicates a wrong approach to some (unknown here) problem is being used.

As an indirect "proof" of the above claim: Would a recursive lock be a common/correct approach to the/some usual situations involving mutexes, it would be sooner or later included in the standard library.

And finally, last but not least: What Russ Cox from the Go development team wrote here https://groups.google.com/d/msg/golang-nuts/XqW1qcuZgKg/Ui3nQkeLV80J:

Recursive (aka reentrant) mutexes are a bad idea.
The fundamental reason to use a mutex is that mutexes
protect invariants, perhaps internal invariants like
"p.Prev.Next == p for all elements of the ring", or perhaps
external invariants like "my local variable x is equal to p.Prev."

Locking a mutex asserts "I need the invariants to hold"
and perhaps "I will temporarily break those invariants."
Releasing the mutex asserts "I no longer depend on those
invariants" and "If I broke them, I have restored them."

Understanding that mutexes protect invariants is essential to
identifying where mutexes are needed and where they are not.
For example, does a shared counter updated with atomic
increment and decrement instructions need a mutex?
It depends on the invariants. If the only invariant is that
the counter has value i - d after i increments and d decrements,
then the atmocity of the instructions ensures the
invariants; no mutex is needed. But if the counter must be
in sync with some other data structure (perhaps it counts
the number of elements on a list), then the atomicity of
the individual operations is not enough. Something else,
often a mutex, must protect the higher-level invariant.
This is the reason that operations on maps in Go are not
guaranteed to be atomic: it would add expense without
benefit in typical cases.

Let's take a look at recursive mutexes.
Suppose we have code like this:

     func F() {
             mu.Lock()
             ... do some stuff ...
             G()
             ... do some more stuff ...
             mu.Unlock()
     }

     func G() {
             mu.Lock()
             ... do some stuff ...
             mu.Unlock()
     }

Normally, when a call to mu.Lock returns, the calling code
can now assume that the protected invariants hold, until
it calls mu.Unlock.

A recursive mutex implementation would make G's mu.Lock
and mu.Unlock calls be no-ops when called from within F
or any other context where the current thread already holds mu.
If mu used such an implementation, then when mu.Lock
returns inside G, the invariants may or may not hold. It depends
on what F has done before calling G. Maybe F didn't even realize
that G needed those invariants and has broken them (entirely
possible, especially in complex code).

Recursive mutexes do not protect invariants.
Mutexes have only one job, and recursive mutexes don't do it.

There are simpler problems with them, like if you wrote

     func F() {
             mu.Lock()
             ... do some stuff
     }

you'd never find the bug in single-threaded testing.
But that's just a special case of the bigger problem,
which is that they provide no guarantees at all about
the invariants that the mutex is meant to protect.

If you need to implement functionality that can be called
with or without holding a mutex, the clearest thing to do
is to write two versions. For example, instead of the above G,
you could write:

     // To be called with mu already held.
     // Caller must be careful to ensure that ...
     func g() {
             ... do some stuff ...
     }

     func G() {
             mu.Lock()
             g()
             mu.Unlock()
     }

or if they're both unexported, g and gLocked.

I am sure that we'll need TryLock eventually; feel free to
send us a CL for that. Lock with timeout seems less essential
but if there were a clean implementation (I don't know of one)
then maybe it would be okay. Please don't send a CL that
implements recursive mutexes.

Recursive mutexes are just a mistake, nothing more than
a comfortable home for bugs.

Russ

When to Use Recursive Mutex