counting_semaphore deadlocks?

[AlexGuteniev]

Bugzilla Link	47013
Version	11.0
OS	Windows NT
CC	@mclow

Extended Description

counting_semaphore::release only notifies waiting thread when count reaches zero. it only notifies one waiting thread if __update == 1:

void release(ptrdiff_t __update = 1)
{
    if(0 < __a.fetch_add(__update, memory_order_release))
        ;
    else if(__update > 1)
        __a.notify_all();
    else
        __a.notify_one();
}

llvm-project/libcxx/include/semaphore

Lines 86 to 94 in 4357986

	void release(ptrdiff_t __update = 1)
	{
	if(0 < __a.fetch_add(__update, memory_order_release))
	;
	else if(__update > 1)
	__a.notify_all();
	else
	__a.notify_one();
	}

counting_semaphore::acquire enters waiting when __a is observed to be zero:

void acquire()
{
    auto const __test_fn = [=]() -> bool {
        auto __old = __a.load(memory_order_relaxed);
        return (__old != 0) && __a.compare_exchange_strong(__old, __old - 1, memory_order_acquire, memory_order_relaxed);
    };
    __cxx_atomic_wait(&__a.__a_, __test_fn);
}

llvm-project/libcxx/include/semaphore

Lines 96 to 103 in 4357986

	void acquire()
	{
	auto const __test_fn = [=]() -> bool {
	auto __old = __a.load(memory_order_relaxed);
	return (__old != 0) && __a.compare_exchange_strong(__old, __old - 1, memory_order_acquire, memory_order_relaxed);
	};
	__cxx_atomic_wait(&__a.__a_, __test_fn);
	}

Now assume two threads are waiting on acquire call:
T1: { s.acquire(); }
T2: { s.acquire(); }

And third thread calls release, to release two times by one:
T3: { s.release(1); s.release(1); }

first release call unblocks one waiting thread. Assume it is T1, and assume that before T1 did compare_exchange_strong, T3 executes the second release call. Since second release observes __a to be 1 (from the previous call), it never releases T2. So T2 stays blocked while __a == 1.

---

If this analysis is correct, I would have called notify_all() for all cases if __a was observed to be 0. Except for counting_semaphore<1> specialization, where it is always safe to call notify_one().

Another alternative could be avoiding 0 < __a.fetch_add check, this will unblock T2 in subsequent release in my example, but it looks like to be less efficient and more complex.

[AlexGuteniev]

Step-by-step recreation:

T1: { s.acquire(); }
T2: { s.acquire(); }
T3: { s.release(1); s.release(1); }

__a == 0

T1: loads 0, enters wait
T2: loads 0, enters wait
T3: fetch add 1, returns 0, now __a == 1
T3: notify_one goes to T1
T1: unblocks from wait
T3: fetch add 1, returns 1, now __a == 2
T3: does not notify anyone
T1: loads 2
T1: cas 2 to 1 successfully
T1: returns from acquire
T2: still waits though __a == 1

[ldionne]

https://reviews.llvm.org/D114119