Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism

From	Peter Zijlstra <peterz@infradead.org>
Newsgroups	linux.kernel
Subject	Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism
Date	2017-03-13 10:30 +0100
Message-ID	<tkusG-6Sd-19@gated-at.bofh.it> (permalink)
References	<theNr-7vq-5@gated-at.bofh.it> <theNs-7vq-17@gated-at.bofh.it> <tioro-lc-23@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

On Tue, Mar 07, 2017 at 03:31:50PM +0100, Thomas Gleixner wrote:
> On Sat, 4 Mar 2017, Peter Zijlstra wrote:
> 
> > The problem with returning -EAGAIN when the waiter state mismatches is
> > that it becomes very hard to proof a bounded execution time on the
> > operation. And seeing that this is a RT operation, this is somewhat
> > important.
> > 
> > While in practise it will be very unlikely to ever really take more
> > than one or two rounds, proving so becomes rather hard.
> 
> Oh no. Assume the following:
> 
> T1 and T2 are both pinned to CPU0. prio(T2) > prio(T1)
> 
> CPU0
> 
> T1 
>   lock_pi()
>   queue_me()  <- Waiter is visible
> 
> preemption
> 
> T2
>   unlock_pi()
>     loops with -EAGAIN forever

So this is true before the last patch; but if we look at the locking
changes brought by that (pasting its changelog here):

Before:

futex_lock_pi()                 futex_unlock_pi()
  unlock hb->lock

                                  lock hb->lock
                                  unlock hb->lock

                                  lock rt_mutex->wait_lock
                                  unlock rt_mutex_wait_lock
                                    -EAGAIN

  lock rt_mutex->wait_lock
  list_add
  unlock rt_mutex->wait_lock

  schedule()

  lock rt_mutex->wait_lock
  list_del
  unlock rt_mutex->wait_lock

                                  <idem>
                                    -EAGAIN

  lock hb->lock


After:

futex_lock_pi()                 futex_unlock_pi()

  lock hb->lock
  lock rt_mutex->wait_lock
  list_add
  unlock rt_mutex->wait_lock
  unlock hb->lock

  schedule()
                                  lock hb->lock
                                  unlock hb->lock
  lock hb->lock
  lock rt_mutex->wait_lock
  list_del
  unlock rt_mutex->wait_lock

                                  lock rt_mutex->wait_lock
                                  unlock rt_mutex_wait_lock
                                    -EAGAIN

  unlock hb->lock


Your T2 (of higher prio) would block on T1's hb->lock and boost T1
(since hb->lock is an rt_mutex).

Alternatively (!PREEMPT_FULL), the interleave cannot happen (when pinned
to a single CPU) because then hb->lock disables preemption, it being a
spinlock.


Unless I need to go drink more wake-up-juice..

Thread

[PATCH -v5 00/14] the saga of FUTEX_UNLOCK_PI wobbles continues Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
  [PATCH -v5 02/14] futex: Add missing error handling to FUTEX_REQUEUE_PI Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
  [PATCH -v5 04/14] futex: Use smp_store_release() in mark_wake_futex() Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
  [PATCH -v5 10/14] futex: Pull rt_mutex_futex_unlock() out from under hb->lock Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
    Re: [PATCH -v5 10/14] futex: Pull rt_mutex_futex_unlock() out from  under hb->lock Thomas Gleixner <tglx@linutronix.de> - 2017-03-07 19:20 +0100
      Re: [PATCH -v5 10/14] futex: Pull rt_mutex_futex_unlock() out from  under hb->lock Peter Zijlstra <peterz@infradead.org> - 2017-03-07 19:50 +0100
  [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
    Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Thomas Gleixner <tglx@linutronix.de> - 2017-03-07 15:40 +0100
      Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Peter Zijlstra <peterz@infradead.org> - 2017-03-07 19:50 +0100
      Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Peter Zijlstra <peterz@infradead.org> - 2017-03-13 10:30 +0100
        Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Thomas Gleixner <tglx@linutronix.de> - 2017-03-13 15:30 +0100
          Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Peter Zijlstra <peterz@infradead.org> - 2017-03-13 16:20 +0100
  [PATCH -v5 11/14] futex,rt_mutex: Introduce rt_mutex_init_waiter() Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
  [PATCH -v5 07/14] futex: Change locking rules Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:10 +0100
    Re: [PATCH -v5 07/14] futex: Change locking rules Thomas Gleixner <tglx@linutronix.de> - 2017-03-07 14:50 +0100
      Re: [PATCH -v5 07/14] futex: Change locking rules Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2017-03-07 18:20 +0100
        Re: [PATCH -v5 07/14] futex: Change locking rules Peter Zijlstra <peterz@infradead.org> - 2017-03-07 19:10 +0100
  [PATCH -v5 06/14] futex,rt_mutex: Provide futex specific rt_mutex API Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:50 +0100
  [PATCH -v5 05/14] futex: Remove rt_mutex_deadlock_account_*() Peter Zijlstra <peterz@infradead.org> - 2017-03-04 11:50 +0100
  [PATCH -v5 08/14] futex: Cleanup refcounting Peter Zijlstra <peterz@infradead.org> - 2017-03-04 12:50 +0100
  [PATCH -v5 03/14] futex: Cleanup variable names for futex_top_waiter() Peter Zijlstra <peterz@infradead.org> - 2017-03-04 12:50 +0100
  [PATCH -v5 12/14] futex,rt_mutex: Restructure rt_mutex_finish_proxy_lock() Peter Zijlstra <peterz@infradead.org> - 2017-03-04 12:50 +0100
    Re: [PATCH -v5 12/14] futex,rt_mutex: Restructure  rt_mutex_finish_proxy_lock() Thomas Gleixner <tglx@linutronix.de> - 2017-03-07 15:50 +0100
      Re: [PATCH -v5 12/14] futex,rt_mutex: Restructure  rt_mutex_finish_proxy_lock() Thomas Gleixner <tglx@linutronix.de> - 2017-03-07 19:50 +0100
      Re: [PATCH -v5 12/14] futex,rt_mutex: Restructure  rt_mutex_finish_proxy_lock() Peter Zijlstra <peterz@infradead.org> - 2017-03-07 19:50 +0100
    [PATCH] futex: move debug_rt_mutex_free_waiter() further down Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2017-03-08 16:40 +0100
      Re: [PATCH] futex: move debug_rt_mutex_free_waiter() further down Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2017-03-08 16:40 +0100
        Re: [PATCH] futex: move debug_rt_mutex_free_waiter() further down Steven Rostedt <rostedt@goodmis.org> - 2017-03-08 17:40 +0100
      Re: [PATCH] futex: move debug_rt_mutex_free_waiter() further down Steven Rostedt <rostedt@goodmis.org> - 2017-03-08 17:30 +0100
      Re: [PATCH] futex: move debug_rt_mutex_free_waiter() further down Peter Zijlstra <peterz@infradead.org> - 2017-03-13 10:20 +0100

csiph-web