[Bug libstdc++/100806] New: deadlock in std::counting_semaphore

[Bug libstdc++/100806] New: deadlock in std::counting_semaphore

[gatroubo at squizzy dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

            Bug ID: 100806
           Summary: deadlock in std::counting_semaphore
           Product: gcc
           Version: 11.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gatroubo at squizzy dot net
  Target Milestone: ---

Hi,

there seems to be some sort of deadlock in std::counting_semaphore. In the
following test program, I create 10 threads, each thread tries to acquire a
semaphore (initial value 4), waits 100ms, and then releases the semaphore:

https://wandbox.org/permlink/Zt3d4EC5vNOXtr9W

Most of the time, the program seems to be in a deadlock after 5 threads
acquired/released the semaphore. When I compile and run the same code with
clang 11.1 I get the expected behavoir (all 10 threads aquire/release the
semaphore and the program exits successfully):

https://wandbox.org/permlink/XjQaoyy9C6uiDYlo

Thanks for your effort to create such a great tool!
-Tobias

[Bug libstdc++/100806] deadlock in std::counting_semaphore

[rodgertq at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

Thomas Rodgers <rodgertq at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-05-28
           Assignee|unassigned at gcc dot gnu.org      |rodgertq at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1

--- Comment #1 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
This is almost certainly a duplicate of
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100334

Which is fixed on master with a backport to releases/gcc-11 but was broken in
GCC 11.1

Will confirm, thanks!

[Bug libstdc++/100806] deadlock in std::counting_semaphore

[rodgertq at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

--- Comment #2 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
I have confirmed that this is new issue, not related to PR100334.

When there are waiting threads and the semaphore attempts to release one of
the waiting threads, the FUTEX_WAKE syscall's return indicates that 1 thread is
woken, as expected, but it is unclear to me why there is no forward progress at
that point.

I have replaced the algorithm with a simplified version (similar to what is in
libc++) and observe the same result. Further investigation is required. I have
submitted an interim patch that forces wake all which appears to address the
issue.

[Bug libstdc++/100806] deadlock in std::counting_semaphore

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Thomas Rodgers <rodgertq@gcc.gnu.org>:

https://gcc.gnu.org/g:e02840c1a92abecd211ffaf05b28329bcb534583

commit r12-1732-ge02840c1a92abecd211ffaf05b28329bcb534583
Author: Thomas Rodgers <rodgert@appliantology.com>
Date:   Tue Jun 22 10:59:07 2021 -0700

    libstdc++: Fix for deadlock in std::counting_semaphore [PR100806]

    libstdc++-v3/ChangeLog:
            PR libstdc++/100806
            * include/bits/semaphore_base.h (__atomic_semaphore::_M_release):
            Force _M_release() to wake all waiting threads.
            * testsuite/30_threads/semaphore/100806.cc: New test.

[Bug libstdc++/100806] deadlock in std::counting_semaphore

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Thomas Rodgers
<rodgertq@gcc.gnu.org>:

https://gcc.gnu.org/g:c24384efbbaeeca3dbc53e7d1226a57bc16e9ad5

commit r11-8638-gc24384efbbaeeca3dbc53e7d1226a57bc16e9ad5
Author: Thomas Rodgers <rodgert@appliantology.com>
Date:   Tue Jun 22 10:59:07 2021 -0700

    libstdc++: Fix for deadlock in std::counting_semaphore [PR100806]

    libstdc++-v3/ChangeLog:
            PR libstdc++/100806
            * include/bits/semaphore_base.h (__atomic_semaphore::_M_release):
            Force _M_release() to wake all waiting threads.
            * testsuite/30_threads/semaphore/100806.cc: New test.

    (cherry picked from commit e02840c1a92abecd211ffaf05b28329bcb534583)

[Bug libstdc++/100806] deadlock in std::counting_semaphore

[rodgertq at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

Thomas Rodgers <rodgertq at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #5 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
I believe this has been fully resolved.

[Bug libstdc++/100806] deadlock in std::counting_semaphore

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100806

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.2