• R
    implement priority inheritance mutexes · 54ca6779
    Rich Felker 提交于
    priority inheritance is a feature to mitigate priority inversion
    situations, where a execution of a medium-priority thread can
    unboundedly block forward progress of a high-priority thread when a
    lock it needs is held by a low-priority thread.
    
    the natural way to do priority inheritance would be with a simple
    futex flag to donate the calling thread's priority to a target thread
    while it waits on the futex. unfortunately, linux does not offer such
    an interface, but instead insists on implementing the whole locking
    protocol in kernelspace with special futex commands that exist solely
    for the purpose of doing PI mutexes. this would require the entire
    "trylock" logic to be duplicated in the timedlock code path for PI
    mutexes, since, once the previous lock holder releases the lock and
    the futex call returns, the lock is already held by the caller.
    obviously such code duplication is undesirable.
    
    instead, I've made the PI timedlock success path set the mutex lock
    count to -1, which can be thought of as "not yet complete", since a
    lock count of 0 is "locked, with no recursive references". a simple
    branch in a non-hot path of pthread_mutex_trylock can then see and act
    on this state, skipping past the code that would check and take the
    lock to the same code path that runs after the lock is obtained for a
    non-PI mutex.
    
    because we're forced to let the kernel perform the actual lock and
    unlock operations whenever the mutex is contended, we have to patch
    things up when it does the wrong thing:
    
    1. the lock operation is not aware of whether the mutex is
       error-checking, so it will always fail with EDEADLK rather than
       deadlocking.
    
    2. the lock operation is not aware of whether the mutex is robust, so
       it will successfully obtain mutexes in the owner-died state even if
       they're non-robust, whereas this operation should deadlock.
    
    3. the unlock operation always sets the lock value to zero, whereas
       for robust mutexes, we want to set it to a special value indicating
       that the mutex obtained after its owner died was unlocked without
       marking it consistent, so that future operations all fail with
       ENOTRECOVERABLE.
    
    the first of these is easy to solve, just by performing a futex wait
    on a dummy futex address to simulate deadlock or ETIMEDOUT as
    appropriate. but problems 2 and 3 interact in a nasty way. to solve
    problem 2, we need to back out the spurious success. but if waiters
    are present -- which we can't just ignore, because even if we don't
    want to wake them, the calling thread is incorrectly inheriting their
    priorities -- this requires using the kernel's unlock operation, which
    will zero the lock value, thereby losing the "owner died with lock
    held" state.
    
    to solve these problems, we overload the mutex's waiters field, which
    is unused for PI mutexes since they don't call the normal futex wait
    functions, as an indicator that the PI mutex is permanently
    non-lockable. originally I wanted to use the count field, but there is
    one code path that needs to access this flag without synchronization:
    trylock's CAS failure path needs to be able to decide whether to fail
    with EBUSY or ENOTRECOVERABLE, the waiters field is already treated as
    a relaxed-order atomic in our memory model, so this works out nicely.
    54ca6779
pthread_mutex_timedlock.c 1.9 KB