[llvm-bugs] [Bug 47013] New: counting_semaphore deadlocks?

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=47013

            Bug ID: 47013
           Summary: counting_semaphore deadlocks?
           Product: libc++
           Version: 11.0
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: gutenev at gmail.com
                CC: llvm-bugs at lists.llvm.org, mclow.lists at gmail.com

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

https://github.com/llvm/llvm-project/blob/4357986b411dd164932c66ebfe4a9cf96a7d74cd/libcxx/include/semaphore#L86-L94


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


https://github.com/llvm/llvm-project/blob/4357986b411dd164932c66ebfe4a9cf96a7d74cd/libcxx/include/semaphore#L96-L103

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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20200806/9d294179/attachment-0001.html>