The approach of storing lock / wake state in the structure of the kernel thread is fairly common.
It's worth noting that the design of turnstiles is quite specific to a monolithic kernel. In a monolithic kernel, you have a data structure for a each thread / process that is cheap to access and the code that accesses it has visibility into the state of all other threads. You can chain together the process representing threads into some list and walk that list.
The futex design (and related things such as FreeBSD's _umtx_op) come from a very different design requirement: that the fast path shouldn't need to touch any scheduler data structures. These store all of the state in the lock (or condition variable or whatever) structure (a 32-bit word in traditional futexes) and allow the scheduler to discover it later. Priority-inheriting locks built on futexes, rather than using one bit to indicate that a lock is held, store the thread ID of the owner in the low bits of the lock. The fast path to acquire a lock is a single atomic compare-and-exchange. Trying to acquire a contended lock requires a system call (or equivalent) and the kernel can easily look up the owning thread by its ID. I'm not sure why the turnstile doesn't do that, rather than requiring a hash lookup.
In CHERIoT RTOS, we have a microkernel-like design, where the functionality of a traditional kernel is finely subdivided into isolated compartments. We decided that a futex should be the only blocking primitive exposed from the scheduler. You can wait on one futex (with the state stored in the thread structure) or on multiple futexes (with the state stored in a pre-allocated multiwaiter object). The design maps interrupts to counters that also function as futexes, so you can handle hardware and software events in the same way and can build a complex set of locks as protocols on top of the futex (flag locks, priority-inheriting flag locks, recursive mutexes, condition variables, barriers, reader-writer locks, and so on).
Author here. First of all, thank you for reading my article and providing insight! As a matter of fact, I was recently discussing your work with other OS people.
I'm not sure why the turnstile doesn't do that, rather than requiring a hash lookup.
I believe you are mixing up finding the owner and finding the PI state. A mutex using a turnstile could store a pointer to the owner directly into its lock word, and that is in fact what most OSes choose to do. The hash table is used to lookup the contention state (turnstile) of that lock, which you need to obtain some way or another to do PI.
One of the key design hallmarks of Solaris was that it made heavy use of blocking mutexes (or locks), in part because they could provide much better latency for high-priority tasks
This is explained a bit further in the article. Blocking locks allow preemption to stay enabled, while spinlocks typically require preemption to be disabled. I was implicitly comparing blocking locks with spinlocks here, though maybe I should've specified that!
david_chisnall | 21 hours ago
The approach of storing lock / wake state in the structure of the kernel thread is fairly common.
It's worth noting that the design of turnstiles is quite specific to a monolithic kernel. In a monolithic kernel, you have a data structure for a each thread / process that is cheap to access and the code that accesses it has visibility into the state of all other threads. You can chain together the process representing threads into some list and walk that list.
The futex design (and related things such as FreeBSD's
_umtx_op) come from a very different design requirement: that the fast path shouldn't need to touch any scheduler data structures. These store all of the state in the lock (or condition variable or whatever) structure (a 32-bit word in traditional futexes) and allow the scheduler to discover it later. Priority-inheriting locks built on futexes, rather than using one bit to indicate that a lock is held, store the thread ID of the owner in the low bits of the lock. The fast path to acquire a lock is a single atomic compare-and-exchange. Trying to acquire a contended lock requires a system call (or equivalent) and the kernel can easily look up the owning thread by its ID. I'm not sure why the turnstile doesn't do that, rather than requiring a hash lookup.In CHERIoT RTOS, we have a microkernel-like design, where the functionality of a traditional kernel is finely subdivided into isolated compartments. We decided that a futex should be the only blocking primitive exposed from the scheduler. You can wait on one futex (with the state stored in the thread structure) or on multiple futexes (with the state stored in a pre-allocated multiwaiter object). The design maps interrupts to counters that also function as futexes, so you can handle hardware and software events in the same way and can build a complex set of locks as protocols on top of the futex (flag locks, priority-inheriting flag locks, recursive mutexes, condition variables, barriers, reader-writer locks, and so on).
rdmsr | 18 hours ago
Author here. First of all, thank you for reading my article and providing insight! As a matter of fact, I was recently discussing your work with other OS people.
I believe you are mixing up finding the owner and finding the PI state. A mutex using a turnstile could store a pointer to the owner directly into its lock word, and that is in fact what most OSes choose to do. The hash table is used to lookup the contention state (turnstile) of that lock, which you need to obtain some way or another to do PI.
Relax | 17 hours ago
Better latency than what, exactly?
rdmsr | 17 hours ago
This is explained a bit further in the article. Blocking locks allow preemption to stay enabled, while spinlocks typically require preemption to be disabled. I was implicitly comparing blocking locks with spinlocks here, though maybe I should've specified that!