Implementing priority inheritance with user-space wait queues

Implementing priority inheritance with user-space wait queues

[Steven Stewart-Gallus]

Hello,

I have been recently working on a library that implements futex
wait-queues in user-space (see
https://sstewartgallus.com/git?p=uevents.git;a=summary .)  The basic
idea is that an event semaphore is implemented by a queue of "notifiers"
that waiters and signallers enqueue and dequeue to and from.  Each
notifier could be implemented in a multitude of ways such as eventfds,
pipes, spinning on a memory location or futexes.  However, while I found
my implementation has several possible performance advantages I also
found that it has trouble properly implementing thread priorities when
used to implement locks.  One could easily extend my implementation by
making each event semaphore have 40 queues (one for each priority) but
properly implementing priority inheritance seems to be difficult.
Because each waiter waits on a separate notifier it seems to me that to
properly implement priority inheritance with futexes I'd have to iterate
over all notifiers on the queue and set their wait location to the PID
of the thread that has currently acquired the lock.  Anyway, I thought it
was an interesting problem dealing with low-level futex stuff that
linux-smp might be interested in.

Thank you,
Steven Stewart-Gallus