[Bug libstdc++/100334] New: atomic<T>::notify_one() sometimes wakes wrong thread

[Bug libstdc++/100334] New: atomic<T>::notify_one() sometimes wakes wrong thread

[m.cencora at gmail dot com]

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

            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 given
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=c++20 -lpthread

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

void verify(bool cond, std::source_location loc =
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] = std::make_unique<std::atomic<T>>(0);

   auto key = get_waiter_key(atomics.a[0].get());
   for (auto i = 1u; i < 4u; ++i)
   {
      while (true)
      {
         auto atom = std::make_unique<std::atomic<T>>(0);
         if (get_waiter_key(atom.get()) == key)
         {
            atomics.a[i] = 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 = create_atomics<char>();

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

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

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

    auto fut3 = 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 test to
pass

    verify(std::future_status::timeout ==
fut0.wait_for(std::chrono::milliseconds{100}));
    verify(std::future_status::timeout ==
fut1.wait_for(std::chrono::milliseconds{100}));
    verify(std::future_status::ready ==
fut2.wait_for(std::chrono::milliseconds{100}));
    verify(std::future_status::timeout ==
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();
}

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[m.cencora at gmail dot com]

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

--- Comment #1 from m.cencora at gmail dot com ---
This test assumes previous waiter implementation (I used gcc-11 available from
Ubuntu 21.04), latest atomic_wait impl has the same problem, it is just that
waiter is selected in a different way, and create_atomics would have to be
adjusted to accordingly (e.g. allocate 49 atomics in a single vector, and
0,16,32,48 instances should share same waiter instance).

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[m.cencora at gmail dot com]

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

--- Comment #2 from m.cencora at gmail dot com ---
I have adapted the test to gcc trunk, but I am not entirely sure it is correct,
because I don't have gcc trunk locally, I was just testing this on wandbox.org

The problem is even bigger here, because it seems that besides wrong thread is
woken up,
also wrong std::atomic<T> instance finishes the wait() call!

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

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


void emptyDeleter(void *)
{}

template <typename T>
struct atomics_sharing_same_waiter
{
   std::atomic<T> tmp[49 * 4] = {};
   std::shared_ptr<std::atomic<T>> a[4] = {
      { &tmp[0], emptyDeleter },
      { &tmp[16 * 4], emptyDeleter },
      { &tmp[32 * 4], emptyDeleter },
      { &tmp[48 * 4], emptyDeleter }
   };
};

constexpr unsigned key(void * a)
{
    constexpr uintptr_t __ct = 16;
        return (uintptr_t(a) >> 2) % __ct;
}

int main()
{
    // all atomic share the same waiter
    atomics_sharing_same_waiter<char> atomics;
    for (auto& atom : atomics.a)
    {
       atom->store(0);
    }

    std::cout << "atom0 " << atomics.a[0].get() << " key " <<
key(atomics.a[0].get()) << '\n';
    std::cout << "atom1 " << atomics.a[1].get() << " key " <<
key(atomics.a[1].get()) << '\n';
    std::cout << "atom2 " << atomics.a[2].get() << " key " <<
key(atomics.a[2].get()) << '\n';
    std::cout << "atom3 " << atomics.a[3].get() << " key " <<
key(atomics.a[3].get()) << '\n';


    verify(&std::__detail::__waiter_pool_base::_S_for(reinterpret_cast<char
*>(atomics.a[0].get())) == 
           &std::__detail::__waiter_pool_base::_S_for(reinterpret_cast<char
*>(atomics.a[1].get())));

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

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

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

    auto fut3 = 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() doesn't help on gcc
trunk

    verify(std::future_status::timeout ==
fut0.wait_for(std::chrono::milliseconds{100}));
    verify(atomics.a[0]->load() == 0);
    verify(std::future_status::timeout ==
fut1.wait_for(std::chrono::milliseconds{100}));
    verify(atomics.a[1]->load() == 0);
    verify(std::future_status::ready ==
fut2.wait_for(std::chrono::milliseconds{100}));
    verify(atomics.a[2]->load() == 1);
    verify(std::future_status::timeout ==
fut3.wait_for(std::chrono::milliseconds{100}));
    verify(atomics.a[3]->load() == 0);

    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();
}

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[m.cencora at gmail dot com]

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

--- Comment #3 from m.cencora at gmail dot com ---
If my analysis is correct then:
 - we need to force __all = true param in __waiter_pool_base::_M_notify,
 - protect from spurious wakeups in __waiter_pool::_M_do_wait by rechecking if
the value has changed from old, if not then wait again

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

--- Comment #4 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
This analysis is likely correct, except for -

"- protect from spurious wakeups in __waiter_pool::_M_do_wait by rechecking if
the value has changed from old, if not then wait again"

An earlier version of this code did this, but was subject to ABA problems, and 
the standard doesn't require that we do this -

"(23.3) — Blocks until it is unblocked by an atomic notifying operation or is
unblocked spuriously."

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[m.cencora at gmail dot com]

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

--- Comment #5 from m.cencora at gmail dot com ---
Actually standard seems to require it - at least to my understanding of wait()
description in  in chapter 31.8.1: it explicitly states that waiting is
performed in a loop, and loop is exited only if value has changed from old.

So when we force notify_all for pooled waiters, then it may happen that a
thread for which value didn't change from 'old' will be woken, so we must
recheck the value.

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-05-01
             Status|UNCONFIRMED                 |ASSIGNED

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

--- Comment #6 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
Created attachment 50728
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50728&action=edit
Fix wrong thread getting notification

I am testing this patch

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #50728|0                           |1
        is obsolete|                            |

--- Comment #7 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
Created attachment 50740
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50740&action=edit
Fix wrong thread getting notification, take 2

This should fix the issue, submitting patch to mailing list.

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |WAITING

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |ASSIGNED

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch

--- Comment #8 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
Candidate patch submitted to mailing list -

https://gcc.gnu.org/pipermail/libstdc++/2021-May/052464.html

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[rodgertq at gcc dot gnu.org]

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

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

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

--- Comment #9 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
Fixed on master, backported to releases/gcc-11

[Bug libstdc++/100334] atomic<T>::notify_one() sometimes wakes wrong thread

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

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