Mutex synchronization in D

There is currently a very long discussion about synchronization in the D newsgroup. It’s so large that I’m really lost when it comes to know who thinks what, who is proposing what and how has retracted what. But reading the whole thing makes me think about what’s inadequate in the current way D wants to do synchronization. So here’s how I’d do synchronization in D if we could get rid of the legacy. Perhaps it’d help someone create a true proposal that can be integrated in the language.

Most of the time when I use a mutex, I want to synchronize access to one or a small number of variables. The following code let you add words to a translation dictionary, and once they’re in there you can confirm each translation using a separate function… all that in a thread-safe manner. The whole class is thread-safe, thanks to the use of two mutexes. This is what I’d do in C++ (skipping constructor for brevity):

class Dictionary
{
    std::map< std::string, std::string > translations;
    boost::mutex translationsMutex;

    int confirmed, unconfirmed;
    boost::mutex confirmedUnconfirmedMutex;

    void addWord(const std::string & word, const std::string & foreignWord)
    {
        boost::unique_lock< boost::mutex > lock(translationsMutex);
        translations[word] = foreignWord;

        boost::unique_lock< boost::mutex > lock(confirmedUnconfirmedMutex);
        ++unconfirmed;
    }

    bool confirmWord(const std::string & word, const std::string & foreignWord)
    {
        {
            boost::unique_lock< boost::mutex > lock(translationsMutex);
            std::map< std::string, std::string > iterator = translations.find(word);
            if (iterator == translations.end())
                return false;
            if (iterator.second != foreignWord)
                return false;
        }

        {
            boost::unique_lock< boost::mutex > lock(confirmedUnconfirmedMutex);
            --unconfirmed;
            ++confirmed;
        }
        globalNotifyWordConfirmed(word, foreignWord);
        return true;
    }
}

Notice how each variable, or each group of variable, has its own lock. The less you protect under one lock, the easier it is to reason about locking. Each lock protects one thing, and is used to protect only that thing. In the addWord function, both mutexes are locked at the same time because the operation needs to be atomic, while this is not the case in confirmWord (because we assume once a word has been added it won’t be replaced by another one later).

Also note that the call to the globalNotifyWordConfirmed function is done outside of any scoped lock. One reason is performance: we simply have no need for the lock at this point. But the bigger reason is to avoid deadlocks. This is important: you need to care about each function you’re calling while you’re locking a mutex. If that function locks a mutex of its own, depending on what locking sequence might happen in other threads you might be creating a potential deadlock. Better call functions outside of locks whenever you can.

Possible Design for D

So obviously, I’d like to do something like this C++ code in D. And with D trying to guard against low-level races, I’d like if it could enforce correct usage of the locks too. So here’s how I’d like to be able to write it in D, purposefully forgetting about how it is done currently to make things easier: make “synchronized” a storage class applicable to variables. Here’s what it’d look like:

class Dictionary
{
    private synchronized string[string] translations;
    private synchronized int confirmed, unconfirmed;

    void addWord(string word, string foreignWord)
    {
        synchronized(translations)
        {
            translations[word] = foreignWord;

            synchronized(unconfirmed)
                ++unconfirmed;
        }
    }

    bool confirmWord(string word, string foreignWord)
    {
        synchronized(translations)
        {
            string * found = word in translation;
            if (!found)
                return false;
            if (*found != foreignWord)
                return false;
        }
        synchronized(unconfirmed, confirmed)
        {
            --unconfirmed;
            ++confirmed;
        }
        globalNotifyWordConfirmed(word, foreignWord);
        return true;
    }
}

Basically, it’s the same thing as in C++, except the mutexes are implicit for any variable with the synchronized storage class. To synchronize on an implicit mutex, synchronize on the variable it is attached to.

Because mutexes are only locked when inside a synchronized block, the globalNotifyWordConfirmed function can be called without any of our mutexes being locked, so it does not matter what mutexes the external function can lock: our mutex will never be involved in a deadlock.

The compiler prevents reads, writes, and passing references to those variables anywhere except in a synchronized block relating to them. Also, the compiler prevents you from passing references to those variables to non-pure functions that might leak them to somewhere outside the synchronized block. Pure functions are fine¹, but any reference returned from these should be tainted and prevented from escaping the synchronized block.

Current Design in D

The current approach in version 2 of D is to mark a whole class as being synchronized, which has the effect of implicitly synchronizing all member functions on an object-level mutex. Thus, you’d write the above code as this:

synchronized class Dictionary
{
    private string[string] translations;
    private int confirmed, unconfirmed;

    void addWord(string word, string foreignWord)
    {
        translations[word] = foreignWord;
        ++unconfirmed;
    }

    bool confirmWord(string word, string foreignWord)
    {
        string * found = word in translation;
        if (!found)
            return false;
        if (*found != foreignWord)
            return false;

        --unconfirmed;
        ++confirmed;

        globalNotifyWordConfirmed(word, foreignWord);
        return true;
    }
}

This certainly looks nicer, although the obvious compromise is that we’ve lost the finer grained locking scheme used previously: both variables are protected by the same mutex attached to the object.

If we really need two locks, we’d need two objects. Another option would be to use the same idiom as in C++: create a mutex object for each group of variable and synchronize on them when needed, but the compiler won’t help you because it does not know the relation between the variables and the mutex, and in fact the safeties against low-level races in the language will make this quite hard.

But the fundamental problem is that the above code is deadlock prone! Even though it’s not quite noticable, because each functions is implicitly wrapped in a synchronized (this) block, we’re calling globalNotifyWordConfirmed while the object mutex is still locked. If this global function locks another mutex, it better not do it while another thread has locked it and is then trying to access our dictionary. Locking two mutexes at once is deadlock prone unless you can ensure they’re locked in always the right order. But since you can’t avoid having the mutex locked because implicit synchronization covers the whole function’s body, you really need to know what the other function at the other end of your program is doing.

I disdain implicit locking, because it encourages you to keep mutexes locked more than necessary, and this can easily result in a deadlock if you’re not careful. Synchronization should happen in your face: you need to be very aware it is happening or you’ll introduce deadlocks in your code.

Shared Mutex

Let’s return to our first example, the one with two mutexes. Notice how the translation variable is only read in the confirmWord function. Since we’re not changing the data structure in any way, it is safe to have two threads read it at the same time.

If I was in C++, I’d use a shared lock to make it possible for multiple threads to read the translations variable at the same time while ensuring only one thread can write to it. In C++, I’d simply change the boost::mutex protecting it for boost::shared_mutex, and use boost::shared_lock instead of boost::unique_lock in the confirmWord function when I only need read access to translations:

class Dictionary
{
    std::map< std::string, std::string > translations;
    boost::shared_mutex translationsMutex;

    int confirmed, unconfirmed;
    boost::mutex confirmedUnconfirmedMutex;

    void addWord(const std::string & word, const std::string & foreignWord)
    {
        boost::unique_lock< boost::mutex > lock(translationsMutex);
        translations[word] = foreignWord;

        boost::unique_lock< boost::mutex > lock(confirmedUnconfirmedMutex);
        ++unconfirmed;
    }

    bool confirmWord(const std::string & word, const std::string & foreignWord)
    {
        {
            boost::shared_lock< boost::mutex > lock(translationsMutex);
            std::map< std::string, std::string > iterator = translations.find(word);
            if (iterator == translations.end())
                return false;
            if (iterator.second != foreignWord)
                return false;
        }

        {
            boost::unique_lock< boost::mutex > lock(confirmedUnconfirmedMutex);
            --unconfirmed;
            ++confirmed;
        }
        globalNotifyWordConfirmed(word, foreignWord);
        return true;
    }
}

How do we do that in D? I propose the use of synchronized (const translations) to mean that we only need read access to the variable, allowing the mutex to be locked in shared mode. const will make sure we’re not writing to the variable in that block². We might also want a way to tell the compiler we’ll need a shared mutex for this variable: we could have synchronized(shared) as a storage class telling us that. Again, very small changes from the original code:

class Dictionary
{
    private synchronized(shared) string[string] translations;
    private synchronized int confirmed, unconfirmed;

    void addWord(string word, string foreignWord)
    {
        synchronized(translations)
        {
            translations[word] = foreignWord;

            synchronized(unconfirmed)
                ++unconfirmed;
        }
    }

    bool confirmWord(string word, string foreignWord)
    {
        synchronized(const translations)
        {
            string * found = word in translation;
            if (!found)
                return false;
            if (*found != foreignWord)
                return false;
        }
        synchronized(unconfirmed, confirmed)
        {
            --unconfirmed;
            ++confirmed;
        }
        globalNotifyWordConfirmed(word, foreignWord);
        return true;
    }
}

Final Remarks

With the approach suggested here, where each variable can be said to be synchronized and have its implicit mutex, you still have the problem that it’s easy to have too many mutexes. In the example above, both confirmed and unconfirmed should really be protected by the same mutex, but I have not made it clear that this is what happens when you declare them as:

synchronized int confirmed, unconfirmed;

I’m actually not sure this is the right syntax for grouping two variables under the same mutex. We might need to figure something else that’d be more obvious to signify that two variables are part of the same mutex.

Another thing to note is that I don’t even need a recursive mutex to make the Dictionary class work. Since I know precisely when the mutex is going to be locked, and I know no one else can lock the mutex, it’s easy to make sure the same thread doesn’t try to lock the mutex twice at the same time. Thus, I can use the simpler kind of mutex that does not have to maintain a lock counter, which of course is slightly more performant. I don’t think this kind of mutex is appropriate as a language default, but it’d be nice to be able to choose this when declaring a synchronized variable.

The End

Hopefully, the ideas floated here will be useful to someone.