Futex-likes

5 minute read

Most major OSes offer some form of futex-like functionality at this point. Some of these are a bit obscure and hard to remember, though, so I thought I’d write some stuff about them down so that I can refer to it or link it later.

Caveat: I’m mostly using “futex-like” to mean relatively the simple wait/wake subset of futex, and not all the other things SYS_futex supports.

I also am assuming you know what futexes are. Eventually I’ll probably ramble about what the APIs look like (mostly so I can explain what I wish they looked like), but this blog post isn’t going to be useful to you if you don’t know this stuff already.

Windows

On Windows you have two choices: keyed events, or the WaitOnAddress API family.

Keyed Events

Keyed events are a ntdll API that’s been around for a long time and used in a lot of code, but… being in ntdll means they’re not considered stable, and technically could change someday. (It’s hard to imagine this happening, but who knows)

Now, keyed events aren’t really as powerful as futexes, but for many things they’re enough, and will be much better than whatever your non-futex fallback would be.

Being unstable, there isn’t official documentation, but this article covers them quite well.

WaitOnAddress

WaitOnAddress, WakeByAddressSingle and WakeByAddressAll are Windows 8 APIs that offer futex-like functionality with fairly few extra bells/whistles.

Usage / Compatibility Concerns

Unfortunately, these both have compatibility downsides.

Keyed events are a ntdll api (which may go away), and WaitOnAddress requires Windows 8, and not all software wants to drop Windows 7 yet.

You can fully cover all bases here by first trying to load the WaitOnAddress functions from their DLL (API-MS-Win-Core-Synch-l1-2-0.dll), and only falling back to using ntdll/keyed events if this fails. The reason I say this covers your bases is that this way you’ll only use the unstable API where the stable one doesn’t exist, which is presumably only on older OS versions (pre Windows 8), which are already released and (hopefully) aren’t going to change.

That said, I think there’s not that bad of a wrong answer here. Keyed events are probably not going anywhere, but also very little is likely lost by dropping Windows 7 support for most code (so just using WaitOnAddress would be fine).

If you have a choice, IMO use WaitOnAddress unconditionally (link with synchronization.lib) and require Windows 8, since it means you don’t need to do any special initialization. For keyed events you’ll need to both load things out of the DLL at initialization time (unless you have an import library for ntdll, which is possible but annoying), and also initialize a global shared HANDLE (which is mostly required when emulating futex on top of keyed events).

Darwin (macOS, iOS, tvOS, watchOS, and more)

There’s an unstable API for this, which is __ulock_wait/__ulock_wake. This has been around since Darwin 16 (in macOS 10.12, iOS 10.0, tvOS 10.0, and watchOS 3.0).

It’s unclear how unstable it is in practice, but “quite unstable” seems like a safe bet. The functions start with several underscores, and this is not provided by any public header file. That said, the functions are publicly exported from libSystem, so they’re completely usable by arbitrary code.

It is in a private header, under bsd/sys/ulock.h (inside the xnu source). You can’t #include this, so you have to just declare this stuff yourself.

If you’re in C or C++, either using the weak_import attribute on your declarations (or lazy-loading with dlsym) seems recommendable so that you can handle older OSes, or future ones where the APIs have gone missing

If you’re using Rust, I wrote a ulock-sys crate for this API that you can use if you’re aware of the caveats. It even has some experimental code (behind a feature) that can load them at runtime using dlsym, but it’s only been briefly smoke tested.

Android

On Android you can use futex like you would on linux, as it is linux. I mention it because there’s a misconception that either futex is unsupported on Android, or that it’s supported but lacking in functionality. This isn’t true.

People think this is basically because the futex.h header on android is pretty busted, and missing a ton of stuff thats fully supported and has been forever. You should define this stuff if it’s missing honestly.

In C or C++ this might look like:

#ifndef SYS_futex
# define SYS_futex __NR_futex
#endif
#ifndef FUTEX_WAIT_BITSET
# define FUTEX_WAIT_BITSET 9
#endif
#ifndef FUTEX_PRIVATE_FLAG
# define FUTEX_PRIVATE_FLAG 128
#endif
// ...

The above should be behind an #ifdef __BIONIC__, or something else that indicates that your futex header is untrustworthy.

In Rust probably just unconditionally define the constants yourself on Android. The libc crate tries to mimic the header files (which are wrong here), and so I would expect it doesn’t have things not in them.

Various BSDs

Most of these seem to have it in one form or another.

OpenBSD literally just calls it futex (man 2 futex). It doesn’t support most of the Linux futex stuff, but it supports the most commonly used pieces.

FreeBSD has _umtx_op which does support the futex operations, as well as essentially every operation offered by a compliant implementation of libpthread.

Dragonfly even has it, in the form of umtx_sleep and umtx_wakeup.

And it turns out that there are actually no other BSDs in existence, and that was all of them. Huh!

Other

A few other places you might be able to find this are:

C++20 added wait and notify operations to their standard library.

On the web platform, JS Atomics object supports wait and notify.

WebAssembly’s threading proposal includes instructions for this as well, discussed here under Wait and Notify operators

The Fuchsia OS has support too, as described in its documentation, which is quite good.

Failing all of that, futex can be implemented with with a global hash table mapping addresses to a wait set (this kind of hash table is also known as a parking lot). Of course, this doesn’t help you if you want futexes in order to implement the wait sets (which certainly isn’t required, but is often desirable).