All of lore.kernel.org
 help / color / mirror / Atom feed
From: Peter Zijlstra <peterz@infradead.org>
To: Thomas Gleixner <tglx@linutronix.de>
Cc: mingo@kernel.org, juri.lelli@arm.com, rostedt@goodmis.org,
	xlpang@redhat.com, bigeasy@linutronix.de,
	linux-kernel@vger.kernel.org, mathieu.desnoyers@efficios.com,
	jdesfossez@efficios.com, bristot@redhat.com,
	dvhart@infradead.org
Subject: Re: [PATCH -v5 14/14] futex: futex_unlock_pi() determinism
Date: Mon, 13 Mar 2017 10:25:42 +0100	[thread overview]
Message-ID: <20170313092542.GJ3343@twins.programming.kicks-ass.net> (raw)
In-Reply-To: <alpine.DEB.2.20.1703071526110.3584@nanos>

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..

  parent reply	other threads:[~2017-03-13  9:25 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-03-04  9:27 [PATCH -v5 00/14] the saga of FUTEX_UNLOCK_PI wobbles continues Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 01/14] futex: Fix potential use-after-free in FUTEX_REQUEUE_PI Peter Zijlstra
2017-03-14 20:48   ` [tip:locking/urgent] " tip-bot for Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 02/14] futex: Add missing error handling to FUTEX_REQUEUE_PI Peter Zijlstra
2017-03-14 20:49   ` [tip:locking/urgent] " tip-bot for Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 03/14] futex: Cleanup variable names for futex_top_waiter() Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 04/14] futex: Use smp_store_release() in mark_wake_futex() Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 05/14] futex: Remove rt_mutex_deadlock_account_*() Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 06/14] futex,rt_mutex: Provide futex specific rt_mutex API Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 07/14] futex: Change locking rules Peter Zijlstra
2017-03-07 13:22   ` Thomas Gleixner
2017-03-07 16:47     ` Sebastian Andrzej Siewior
2017-03-07 18:01       ` Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 08/14] futex: Cleanup refcounting Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 09/14] futex: Rework inconsistent rt_mutex/futex_q state Peter Zijlstra
2017-03-07 13:26   ` Thomas Gleixner
2017-03-04  9:27 ` [PATCH -v5 10/14] futex: Pull rt_mutex_futex_unlock() out from under hb->lock Peter Zijlstra
2017-03-07 14:08   ` Thomas Gleixner
2017-03-07 18:01     ` Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 11/14] futex,rt_mutex: Introduce rt_mutex_init_waiter() Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 12/14] futex,rt_mutex: Restructure rt_mutex_finish_proxy_lock() Peter Zijlstra
2017-03-07 14:18   ` Thomas Gleixner
2017-03-07 17:57     ` Peter Zijlstra
2017-03-07 17:59       ` Thomas Gleixner
2017-03-08 15:29   ` [PATCH] futex: move debug_rt_mutex_free_waiter() further down Sebastian Andrzej Siewior
2017-03-08 15:37     ` Sebastian Andrzej Siewior
2017-03-08 16:21       ` Steven Rostedt
2017-03-08 16:20     ` Steven Rostedt
2017-03-13  9:16     ` Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 13/14] futex: Rework futex_lock_pi() to use rt_mutex_*_proxy_lock() Peter Zijlstra
2017-03-04  9:27 ` [PATCH -v5 14/14] futex: futex_unlock_pi() determinism Peter Zijlstra
2017-03-07 14:31   ` Thomas Gleixner
2017-03-07 17:59     ` Peter Zijlstra
2017-03-13  9:25     ` Peter Zijlstra [this message]
2017-03-13 14:25       ` Thomas Gleixner
2017-03-13 15:11         ` Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20170313092542.GJ3343@twins.programming.kicks-ass.net \
    --to=peterz@infradead.org \
    --cc=bigeasy@linutronix.de \
    --cc=bristot@redhat.com \
    --cc=dvhart@infradead.org \
    --cc=jdesfossez@efficios.com \
    --cc=juri.lelli@arm.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mathieu.desnoyers@efficios.com \
    --cc=mingo@kernel.org \
    --cc=rostedt@goodmis.org \
    --cc=tglx@linutronix.de \
    --cc=xlpang@redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.