Page MenuHomeFreeBSD

Add a futex implementation for CloudABI.
ClosedPublic

Authored by ed on Jul 22 2015, 10:28 AM.
Tags
None
Referenced Files
Unknown Object (File)
Thu, Nov 28, 7:31 PM
Unknown Object (File)
Thu, Nov 28, 7:30 PM
Unknown Object (File)
Thu, Nov 28, 3:48 AM
Unknown Object (File)
Thu, Nov 28, 3:46 AM
Unknown Object (File)
Nov 5 2024, 8:36 PM
Unknown Object (File)
Oct 20 2024, 9:42 AM
Unknown Object (File)
Oct 20 2024, 9:42 AM
Unknown Object (File)
Oct 20 2024, 9:42 AM
Subscribers

Details

Summary

CloudABI provides two different types of futex objects: read-write locks
and condition variables. There is no need to provide separate support
for once objects and thread joining, as these are efficiently simulated
by blocking on a read-write lock. Mutexes simply use read-write locks.

Condition variables always have a lock object associated to them. They
always know to which lock a thread needs to be migrated if woken up.
This allows us to implement requeueing. A broadcast on a condition
variable will never cause multiple threads to be woken up at once. They
will be woken up iteratively.

This implementation still has lots of room for improvement. Locking is
coarse and right now we use linked lists to store all of the locks and
condition variables, instead of using a hash table. The primary goal of
this implementation was to behave correctly. Performance will be
improved as we go.

Test Plan

This futex implementation has been in use for the last couple of months
and seems to work pretty well. All of the cloudlibc and libc++ unit
tests seem to pass.

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

ed retitled this revision from to Add a futex implementation for CloudABI..
ed updated this object.
ed edited the test plan for this revision. (Show Details)
ed added reviewers: dchagin, kib.

Fix some minor nits.

  • Properly test for overflow in convert_timestamp_relative().
  • Fix bad comments.

Is this thing API-compatible with the real linux futexes ? If not, the name is confusing.

Did you considered using kern_umtx.c in some way ? The implementation is too similar to not ask this.

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

Why do you need to compare address spaces ?

In D3148#63488, @kib wrote:

Is this thing API-compatible with the real linux futexes ? If not, the name is confusing.

I was under the impression that "futex" was sort of a generic name for this model. To be honest, I wouldn't know what other name to pick. Suggestions are welcome!

Did you considered using kern_umtx.c in some way ? The implementation is too similar to not ask this.

That's a good question! I looked into kern_umtx.c in detail when I started working on this. Though it doesn't do requeueing, I think it's a really nice implementation.

At around the time I was working on this, I was also looking into adding CloudABI support to Linux and NetBSD. I had to make the decision whether to extend the OS native primitives or have a custom implementation. I decided to do the latter; this version also works on NetBSD and Linux with just some minor modifications. It has allowed me to get threading working on these systems from early on. A new implementation for NetBSD was needed anyway, as it doesn't seem to support futexes in the first place.

That said, if there's a way to unify this with umtx some way, I'd love to see that happen eventually. This implementation is only meant to get us off the ground. If you like, I can add this as a TODO to the top of the source file.

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

Just like kern_umtx.c, this implementation skips vm_map_lookup() in case the object is process-local. For process-local locks we key by vmspace and virtual address. For global locks we key by vmobject and offset.

Only one of fa_vmspace and fa_vmobject is set.

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

Assume that you have some object, e.g. file or anonymous shared memory, shared-mapped at two different places in your process, and carrying a local futex. Should it work when updated from either address ? Note that underlying memory is modifyable from both locations.

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

As soon as you start to place the object in a piece of shared memory (mapped more than once, which may be in the same process or not), you can no longer use CLOUDABI_FUTEXSCOPE_PROCESS_LOCAL. It should work if you use CLOUDABI_FUTEXSCOPE_GLOBAL.

To confess, I hadn't thought of the case where a single process maps the same piece of memory multiple times. Taking that into account, PROCESS_LOCAL is a misnomer. Naming it after the mmap() flags, PRIVATE and SHARED would make more sense. This is actually what POSIX itself uses. What do you think?

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

My point is that a futex is a region of memory. Same regions imply that this is the same futex. An implementation should store fa_vmobject and offset into the object. Then you could compare process (and not vmspace) ownership if you want to ensure process-private scope, after you found the kernel object after looking up the backing object and offset.

At least the approach would not mix layers.

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

I tried sending this response earlier today by email, but it looks like our Phabricator instance doesn't support this yet. So here it goes again:

My observation was that purely matching the VM objects doesn't work. If a thread calls fork() while another thread is waiting on a futex, it will never be woken up, as shadow objects are inserted in between. This is why I'm falling back to the vmspace for private mappings.

Additional note: the scopes are not intended to act as access controls in any way. They are purely there as a hint, so that the kernel doesn't need to call into vm_map_lookup() unconditionally.

sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

What you wrote above should be made into a comment explaining both mutual exclusivity for vmspace/object, and for all other points.

Clarify process local vs process shared locks.

  • Remove the poorly named CLOUDABI_FUTEXSCOPE_PROCESS_LOCAL. Even for locks that are local to processes but are mapped multiple times, we need CLOUDABI_FUTEXSCOPE_GLOBAL. Simply use the mmap()-style PRIVATE and SHARED suffixes.
  • Extend comments to explain why we need the keying by vmspace, due to forks inserting shadow VM objects.
sys/compat/cloudabi/cloudabi_futex.c
283 ↗(On Diff #7168)

Done!

I've also removed the poorly named CLOUDABI_FUTEXSCOPE_* flags. The changes to the syscalldefs_m* and the system call table will be committed separately.

I do not want to read too much of this implementation. Consider that I am fine with what I see at the outer perimeter of the code.

This revision was automatically updated to reflect the committed changes.
In D3148#63495, @ed wrote:
In D3148#63488, @kib wrote:

Did you considered using kern_umtx.c in some way ? The implementation is too similar to not ask this.

That's a good question! I looked into kern_umtx.c in detail when I started working on this. Though it doesn't do requeueing, I think it's a really nice implementation.

At around the time I was working on this, I was also looking into adding CloudABI support to Linux and NetBSD. I had to make the decision whether to extend the OS native primitives or have a custom implementation. I decided to do the latter; this version also works on NetBSD and Linux with just some minor modifications. It has allowed me to get threading working on these systems from early on. A new implementation for NetBSD was needed anyway, as it doesn't seem to support futexes in the first place.

That said, if there's a way to unify this with umtx some way, I'd love to see that happen eventually. This implementation is only meant to get us off the ground. If you like, I can add this as a TODO to the top of the source file.

One thing I fixed a while back in the Linux ABI was to re-use the umtx_key implementation in the Linux futex code instead of duplicating that portion of the logic. Assuming that those bits of your implementation are OS-dependent and not shared you could keep the actual bit-fiddling bits your own (and shared across OS's perhaps) but possibly reduce duplication in the FreeBSD-specific bits by using umtx keys directly.

In D3148#65928, @jhb wrote:

One thing I fixed a while back in the Linux ABI was to re-use the umtx_key implementation in the Linux futex code instead of duplicating that portion of the logic. Assuming that those bits of your implementation are OS-dependent and not shared you could keep the actual bit-fiddling bits your own (and shared across OS's perhaps) but possibly reduce duplication in the FreeBSD-specific bits by using umtx keys directly.

That sounds like a good idea. I just sent you code review D3286 to let the CloudABI futex code use umtx keys.