From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
 id 10A7F3AA9C55; Thu, 29 Apr 2021 13:22:58 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 10A7F3AA9C55
From: "m.cencora at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/100334] New: atomic<T>::notify_one() sometimes wakes
 wrong thread
Date: Thu, 29 Apr 2021 13:22:57 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 11.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: m.cencora at gmail dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-100334-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-BeenThere: gcc-bugs@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-bugs mailing list <gcc-bugs.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Thu, 29 Apr 2021 13:22:58 -0000

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

            Bug ID: 100334
           Summary: atomic<T>::notify_one() sometimes wakes wrong thread
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: m.cencora at gmail dot com
  Target Milestone: ---

If waiter pool implementation is used in std::atomic<T>::wait/notify for gi=
ven
T, then notify_one must underneath call notify_all to make sure that proper
thread is awaken.
I.e. if multiple threads call atomic<T>::wait() on different atomic<T>
instances, but all of them share same waiter, then notify_one on only one of
atomics will possibly wake the wrong thread.
This can lead to program hangs, deadlocks, etc.

Following test app reproduces the bug:
g++-11 -std=3Dc++20 -lpthread

#include <atomic>
#include <future>
#include <iostream>
#include <source_location>
#include <thread>
#include <vector>

void verify(bool cond, std::source_location loc =3D
std::source_location::current())
{
    if (!cond)
    {
        std::cout << "Failed at line " << loc.line() << '\n';
        std::abort();
    }
}

template <typename T>
struct atomics_sharing_same_waiter
{
   std::unique_ptr<std::atomic<T>> a[4];
};

unsigned get_waiter_key(void * ptr)
{
   return std::_Hash_impl::hash(ptr) & 0xf;
}

template <typename T>
atomics_sharing_same_waiter<T> create_atomics()
{
   std::vector<std::unique_ptr<std::atomic<T>>> non_matching_atomics;

   atomics_sharing_same_waiter<T> atomics;
   atomics.a[0] =3D std::make_unique<std::atomic<T>>(0);

   auto key =3D get_waiter_key(atomics.a[0].get());
   for (auto i =3D 1u; i < 4u; ++i)
   {
      while (true)
      {
         auto atom =3D std::make_unique<std::atomic<T>>(0);
         if (get_waiter_key(atom.get()) =3D=3D key)
         {
            atomics.a[i] =3D std::move(atom);
            break;
         }
         else
         {
            non_matching_atomics.push_back(std::move(atom));
         }
      }
   }

   return atomics;
}


int main()
{
    // all atomic share the same waiter
    auto atomics =3D create_atomics<char>();

    auto fut0 =3D std::async(std::launch::async, [&] {
        atomics.a[0]->wait(0);
    });

    auto fut1 =3D std::async(std::launch::async, [&] {
        atomics.a[1]->wait(0);
    });

    auto fut2 =3D std::async(std::launch::async, [&] {
        atomics.a[2]->wait(0);
    });

    auto fut3 =3D std::async(std::launch::async, [&] {
        atomics.a[3]->wait(0);
    });

    // make sure the all threads already await
    std::this_thread::sleep_for(std::chrono::milliseconds{100});

    atomics.a[2]->store(1);
    atomics.a[2]->notify_one(); // changing to notify_all() allows this tes=
t to
pass

    verify(std::future_status::timeout =3D=3D
fut0.wait_for(std::chrono::milliseconds{100}));
    verify(std::future_status::timeout =3D=3D
fut1.wait_for(std::chrono::milliseconds{100}));
    verify(std::future_status::ready =3D=3D
fut2.wait_for(std::chrono::milliseconds{100}));
    verify(std::future_status::timeout =3D=3D
fut3.wait_for(std::chrono::milliseconds{100}));

    atomics.a[0]->store(1);
    atomics.a[0]->notify_one();
    atomics.a[1]->store(1);
    atomics.a[1]->notify_one();
    atomics.a[3]->store(1);
    atomics.a[3]->notify_one();
}=