November 06, 2018

Implementing Rust’s std::sync::Mutex in D


The first time I encountered a mutex in C++ I was puzzled. It made no sense to me at all that I was locking one to protect some data and the only way to indicate what data was protected by a certain mutex was a naming convention. It seemed to me like a recipe for disaster, and of course, it is.

I’ve hardly written any code in Rust, in fact only one project to learn the basics of the language. But the time I spent with it was enough to marvel at std::sync::Mutex – at last it made sense! Access to the variable has to go through the mutex’s API, and no convention is needed. And, of course, in the Rust tradition said access is safe.

That unsurprisingly made me slightly jealous. In D, shared is a keyword and it protects the programmer from inadvertently accessing shared state in an unsafe manner (mostly). Atomic operations typically take a pointer to a shared T, but larger objects (i.e. user-defined structs) are usually dealt with by locking a mutex, casting away shared and then using the object as thread-local. While this works, it’s tedious, error-prone, and certainly not safe. Since imitation is the highest form of flattery, I decided to shamelessly copy, as much as possible, the idea behind Rust’s Mutex.

Rust makes the API safe via the borrow checker, but D doesn’t have that. It does, however, have the sort-of-still-experimental DIP1000, which is similar in what it tries to achieve. I set out to use the new functionality to try and devise a safe way to avoid the current practice of BYOM (Bring Your Own Mutex).

I started off by reading the concurrency part of The Rust Book, which was very helpful. It even explains implementation details such as the fact that .borrow returns a smart pointer instead of the wrapped type. This too I copied. I then started thinking of ways to use D’s scope to emulate Rust’s borrow checker. The idea wasn’t to have the same semantics but to enable safe usage and fail to compile unsafe code. Pragmatism was key.

I was initially confused about why std::sync::Mutex is nearly always used with std::sync::Arc – it took me writing a bug to realise that shared data is never allocated on the stack. Obvious in retrospect but I somehow failed to realise that. Since Rust doesn’t have a mark-and-sweep GC, the only real option is to use reference counting for the heap-allocated shared data. This realisation led to another: in D there’s a choice between reference counting and simply using GC-allocated memory, so the API reflects that. The RC version is even @nogc!

The API forces the initialisation of the user-defined type to happen by passing parameters to the constructor of that type. This is because passing an extant object isn’t safe – other references to it may exist in the program and data races could occur. Rust can do this and guarantee at compile-time that other mutable references don’t exist, but D can’t, hence the restriction. For types without mutable indirections the restriction is lifted, made possible by D’s world class static reflection capabilities. The API also enforces that the type is shared – there’s no point to using this library if the type isn’t, and even less of a point making the user type `shared T` all the time.

Although D has an actor model message passing library in std.concurrency, none of the functions are @safe. I also realised it would be trivial to write a deadlock by sending the shared data while a mutex is held to another thread. To fix both of these issues, the library I wrote has @safe versions of D’s concurrency primitives, and the send function checks to see if the mutex is locked before actually passing the compound (mutex, T) type (named Exclusive in the library) to another thread of execution.

DIP1000 itself was hard to understand. I ended up reading the proposal several times, and it didn’t help that the current implementation doesn’t match that document 100%. In the end, however, the result seems to work:

It’s possible that, due to bugs in DIP1000 or in fearless itself that a programmer can break safety, but to the extent of my knowledge this brings @safe concurrent code to D.

I’d love it if any concurrency experts could try and poke holes in the library so I can fix them.

November 05, 2018

New Blog

In case you’ve been wondering why I haven’t posted anything here for the past 3½ years - well, it’s certainly not due to there being nothing to post. The true reason is that, simply put, my dislike for WordPress has surpassed the desire to document what I’ve been doing. And so, as my backlog of things to document grew, the priority of having a way to do it that doesn’t force me to suffer a mediocre WYSIWYG editor and the limits of browser textarea / HTML editing also grew to the point where it could not be delayed further.