[Bug nptl/16892] New: Invalid futex demotion in __lll_timedlock

[Bug nptl/16892] New: Invalid futex demotion in __lll_timedlock

[bernie.ogden at linaro dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

            Bug ID: 16892
           Summary: Invalid futex demotion in __lll_timedlock
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: nptl
          Assignee: unassigned at sourceware dot org
          Reporter: bernie.ogden at linaro dot org
                CC: drepper.fsp at gmail dot com

Following description culled from Carlos O'Donell's analysis at
https://sourceware.org/ml/libc-ports/2013-02/msg00021.html.

Some platforms (m68k, aarch64, arm, sh/sh4) have an implementation of
__lll_timedlock that sets futex to 1 without first checking that it is 0. This
allows the futex to move from 2 (locked with waiters) to 1 (locked with no
waiters) on these platforms.

This does not create a correctness problem, but it does create a pair of
performance problems.

1) Up to N threads can fail to sleep when they ought to have done, where N is
the number of threads expecting futex==2. For example:

* T1 calls __lll_timedlock setting futex to 1 and taking the lock.
* T2 calls __lll_timedlock setting futex to 1 but does not take the lock.
* T2 calls __lll_timedlock_wait and sets the futex to 2 and does not
gain the lock.
* T3 calls __lll_timedlock setting futex to 1 but does not take the lock.
* T2 calls lll_futex_time_wait but fails with -EWOULDBLOCK because T3 reset
futex to 1.
-> One inflight thread (T2), and one spurious failed futex wait syscall.
* T2 again sets the futex to 2 and does not gain the lock.
* ... T2 and T3 go on to call futex wait syscall and both sleep.

2) __lll_unlock only wakes if futex was > 1 prior to release. Thus it can
happen that __lll_timedlock keeps setting futex from 2 to 1 just prior to
__lll_unlock calls, preventing waiters from being awoken. This certainly
affects m68k, arm and aarch64 - sh may also be affected but it's a little
harder to tell as its written in asm.

In both cases, the solution is simply to do an atomic_compare_and_exchange_acq
(as the unaffected platforms already do), rather than an atomic_exchange_acq,
so that __lll_timedlock does not change futex from 2 to 1. It's easy to apply
this fix to at least the targets that are implemented in C. Better still would
be to combine as many as possible of the lowlevellock.h implementations into a
generic implementation that behaves in this way.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[bernie.ogden at linaro dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

Bernard Ogden <bernie.ogden at linaro dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at sourceware dot org   |bernie.ogden at linaro dot org

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[bernie.ogden at linaro dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

Bernard Ogden <bernie.ogden at linaro dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://sourceware.org/bugz
                   |                            |illa/show_bug.cgi?id=15119

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[cvs-commit at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

--- Comment #1 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, master has been updated
       via  4e75751cbbd47242946f817111066f511dbba739 (commit)
      from  bb2ce416563a61bb065f92e022dfd231097d90b6 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=4e75751cbbd47242946f817111066f511dbba739

commit 4e75751cbbd47242946f817111066f511dbba739
Author: Bernard Ogden <bernie.ogden@linaro.org>
Date:   Mon Aug 11 15:26:48 2014 +0100

    Check value of futex before updating in __lll_timedlock

    2014-08-12  Bernard Ogden  <bernie.ogden@linaro.org>

        [BZ #16892]
        * sysdeps/nptl/lowlevellock.h (__lll_timedlock): Use
        atomic_compare_and_exchange_bool_acq rather than atomic_exchange_acq.

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog                   |    6 ++++++
 sysdeps/nptl/lowlevellock.h |    5 ++++-
 2 files changed, 10 insertions(+), 1 deletions(-)

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[cvs-commit at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

--- Comment #2 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, master has been updated
       via  7fda3e6f16aa2efaf3f156c996c6b8f334884252 (commit)
      from  4e75751cbbd47242946f817111066f511dbba739 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=7fda3e6f16aa2efaf3f156c996c6b8f334884252

commit 7fda3e6f16aa2efaf3f156c996c6b8f334884252
Author: Will Newton <will.newton@linaro.org>
Date:   Tue Aug 12 13:01:13 2014 +0100

    Add BZ #16892 to NEWS

-----------------------------------------------------------------------

Summary of changes:
 NEWS |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[will.newton at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

Will Newton <will.newton at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |will.newton at gmail dot com
         Resolution|---                         |FIXED

--- Comment #3 from Will Newton <will.newton at gmail dot com> ---

Fixed in commit 4e75751cbbd47242946f817111066f511dbba739

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/16892] Invalid futex demotion in __lll_timedlock

[bernie.ogden at linaro dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=16892

--- Comment #4 from Bernard Ogden <bernie.ogden at linaro dot org> ---
Still not fixed for sh - raised 17337 on sh-only.

-- 
You are receiving this mail because:
You are on the CC list for the bug.