Skip to content

RFC: futex: requeue pi implementation

Darren Hart lkml 3 versions – In review

Get series with b4
b4 am 20090403203832.9772.21410.stgit@Aeon

Versions newest first · linked by author and title

  1. v7 Latest9 patches 5 repliesIn review
  2. v68 patches 14 repliesSuperseded
  3. v1 RFC7 patches 19 repliesSuperseded

Patches in v7 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/9RFC: futex: futex_wait_queue_me()kernel/futex.c+76 -620 replies
2/9RFC: futex: futex_top_waiter()kernel/futex.c+19 -00 replies
3/9RFC: futex: futex_lock_pi_atomic()kernel/futex.c+130 -940 replies
4/9RFC: futex: fixup_owner()kernel/futex.c+89 -690 replies
5/9RFC: rt_mutex: add proxy lock routineskernel/rtmutex.c kernel/rtmutex_common.h+195 -530 replies
6/9RFC: futex: Add FUTEX_HAS_TIMEOUT flag to restart.futex.flagskernel/futex.c+8 -40 replies
7/9RFC: futex: Add requeue_futex() callkernel/futex.c+29 -140 replies
8/9RFC: futex: add futex_wait_setup()kernel/futex.c+72 -440 replies
9/9RFC: futex: add requeue_pi callsinclude/linux/futex.h include/linux/thread_info.h kernel/futex.c+510 -200 replies

Reviews trailers per patch

3 of 9 patches have a Reviewed-by or Acked-by.

PatchSteven Rostedt
1/9R-b
2/9R-b
3/9R-b
4/9
5/9
6/9
7/9
8/9
9/9

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v7 thread

Cover letter [tip PATCH v7 0/9] RFC: futex: requeue pi implementation

The following series is v7 of the requeue_pi patches against linux-2.6-tip/core/futexes. The current futex implementation doesn't allow for requeueing of PI futexes, which leads to a thundering herd during pthread_cond_broadcasa()t (as opposed to a civilized priority ordered wakeup sequence). The core of the problem is that the underlying rt_mutex cannot be left with waiters and no owner (which would break the PI logic). This patch series updates the futex code to allow for requeueing from non-PI to PI futexes in support of PI aware pthread_cond_* calls along with some needful rt_mutex helper routines. The credit for the conceptual design goes to Thomas Gleixner, while the bugs and other idiocies present in this implementation should be attributed to me.

New in V7:
-refactored futex_wait_requeue_pi()
-fixed pi_state handling for some corner cases in the wake-up path -fixed a wakeup race bug introduced by refactoring futex_wait_queue_me() -corrected a bug in futex_wait_requeue_pi() calling fixup_owner on the wrong
uaddr
-rewrote finish_futex_lock_pi() as fixup_owner() with more intuitive logic -fixed a couple logic errors
-cleaned up some comments and clarified some locking approaches

This version has been tested with a rough raw futex syscall test case as well as with a preliminary glibc patch that updates the pthread_cond* calls to use the new syscalls and allow for the PI calls to take ownership of the rt_mutex inside the kernel (see the "glibc hacks for requeue_pi" at the end of this series). With this patched glibc the LTP realtime/func/prio-wake test case has passes consistently[1] (whereas before it would fail 10% of the time). prio-wake tests the priority ordered wakeup of a pthread_cond_broadcast() using a PI mutex. I have exercised the timeout and signal paths of futex_wait_requeue_pi() prior to requeue. I am working to add more sophisticated tests to be able to exercise the post-requeue error paths as well. Additionally, I'd like to add some fault-injection.

I'd really appreciate feedback on the implementation as well as any design critique. Answers to the questions posed in the patch headers and code comments are particularly welcome.

1. In the interest of full disclosure I should mention that I have seen an rare hang of the prio-wake testcase. Upon closer inspection I now believe this to be due to a race inherent in the testcase, and not due to any flaw in the kernel.

Cc Thomas Gleixner <[email protected]>
Cc Sripathi Kodi <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc John Stultz <[email protected]>
Cc Steven Rostedt <[email protected]>
Cc Dinakar Guniguntala <[email protected]>
Cc Ulrich Drepper <[email protected]>
Cc Eric Dumazet <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Jakub Jelinek <[email protected]>

---

Darren Hart (9):
RFC: futex: add requeue_pi calls
RFC: futex: add futex_wait_setup()
RFC: futex: Add requeue_futex() call
RFC: futex: Add FUTEX_HAS_TIMEOUT flag to restart.futex.flags
RFC: rt_mutex: add proxy lock routines
RFC: futex: fixup_owner()
RFC: futex: futex_lock_pi_atomic()
RFC: futex: futex_top_waiter()
RFC: futex: futex_wait_queue_me()

 include/linux/futex.h       |    8 
 include/linux/thread_info.h |    3 
 kernel/futex.c              | 1179 +++++++++++++++++++++++++++++++++----------
 kernel/rtmutex.c            |  240 +++++++--
 kernel/rtmutex_common.h     |    8 
 5 files changed, 1103 insertions(+), 335 deletions(-)
Signature · 3 lines
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team