linux-kernel - Re: PI futexes + lock stealing woes

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Fri, 1 Dec 2017 12:11:15 -0800
From:   Darren Hart <dvhart@...radead.org>
To:     Julia Cartwright <julia@...com>
Cc:     Thomas Gleixner <tglx@...utronix.de>,
        Peter Zijlstra <peterz@...radead.org>,
        Gratian Crisan <gratian.crisan@...com>,
        linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>
Subject: Re: PI futexes + lock stealing woes

On Wed, Nov 29, 2017 at 11:56:05AM -0600, Julia Cartwright wrote:
> Hey Thomas, Peter-
> 
> Gratian and I have been debugging into a nasty and difficult race w/
> futexes seemingly the culprit.  The original symptom we were seeing
> was a seemingly spurious -EDEADLK from a futex(LOCK_PI) operation.
> 
> On further analysis, however, it appears the thread which gets the
> spurious -EDEADLK has observed a weird futex state: a prior
> futex(WAIT_REQUEUE_PI) operation has returned -ETIMEDOUT, but the uaddr2
> futex word owner field indicates that it's the owner.
> 

Do you have a reproducer you can share?

> Here's an attempt to boil down this situation into a pseudo trace; I'm
> happy to forward along the full traces as well, if that would be
> helpful:

Please do forward the full trace

> 
>    waiter                                  waker                                            stealer (prio > waiter)
> 
>    futex(WAIT_REQUEUE_PI, uaddr, uaddr2,
>          timeout=[N ms])
>       futex_wait_requeue_pi()
>          futex_wait_queue_me()
>             freezable_schedule()
>             <scheduled out>
>                                            futex(LOCK_PI, uaddr2)
>                                            futex(CMP_REQUEUE_PI, uaddr,
>                                                  uaddr2, 1, 0)
>                                               /* requeues waiter to uaddr2 */
>                                            futex(UNLOCK_PI, uaddr2)
>                                                  wake_futex_pi()
>                                                     cmp_futex_value_locked(uaddr, waiter)
>                                                     wake_up_q()
>            <woken by waker>
>            <hrtimer_wakeup() fires,
>             clears sleeper->task>
>                                                                                            futex(LOCK_PI, uaddr2)
>                                                                                               __rt_mutex_start_proxy_lock()
>                                                                                                  try_to_take_rt_mutex() /* steals lock */
>                                                                                                     rt_mutex_set_owner(lock, stealer)
>                                                                                               <preempted>
>          <scheduled in>
>          rt_mutex_wait_proxy_lock()


>             __rt_mutex_slowlock()
>                try_to_take_rt_mutex() /* fails, lock held by stealer */
>                if (timeout && !timeout->task)
>                   return -ETIMEDOUT;
>             fixup_owner()
>                /* lock wasn't acquired, so,
>                   fixup_pi_state_owner skipped */
>    return -ETIMEDOUT;
> 
>    /* At this point, we've returned -ETIMEDOUT to userspace, but the
>     * futex word shows waiter to be the owner, and the pi_mutex has
>     * stealer as the owner */
> 

eeeeeeewwwweeee


>    futex_lock(LOCK_PI, uaddr2)
>      -> bails with EDEADLK, futex word says we're owner.
> 
> At some later point in execution, the stealer gets scheduled back in and
> will do fixup_owner() which fixes up the futex word, but at that point
> it's too late: the waiter has already observed the wonky state.
> 
> fixup_owner() used to have additional seemingly relevant checks in place
> that were removed 73d786bd043eb ("futex: Rework inconsistent
> rt_mutex/futex_q state").

This and the subsequent changes moving some of this out from under the hb->lock
are interesting - and were quite fun to review at the time. Hrm.

I'll continue paging this stuff in, although I suspect Peter will likely beat me
to it. In the meantime, if you can share the reproducer and/or the trace you
collected, that will be helpful.

> 
> The actual kernel we've been testing is 4.9.33-rt23, w/ 153fbd1226fb3
> ("futex: Fix more put_pi_state() vs. exit_pi_state_list() races")

And this does not exhibit the behavior above, correct?

> cherry-picked w/ PREEMPT_RT_FULL.  However, it appears that this issue
> may affect v4.15-rc1?

And this does?

> 
> Thoughts on how to move forward?
> 
> Nasty.
> 
>    Julia
> 

-- 
Darren Hart
VMware Open Source Technology Center