Bug#810868: threads: condition_variable or atomic causes _sometimes_ a deadlock

[U.Mutlu]

Package: g++-4.9
Version: 4.9.2-10
Severity: normal

Dear Maintainer,

there is a mysterious bug in g++ or its libraries.
The bug happens when one compiles and executes the following test code multiple
times:
sometimes the executable just hangs, ie. a deadlock happens.
I think the error lies not in the test code, but in the g++ libraries or even
in g++ itself.

/*
test.cpp

2016-01-13-We
Author: U.Mutlu

condition variable example (but is [sometimes] buggy)

Code adapted from the example at [1]

Question:
  How to fix this code?
  --> it could be a low-level issue, ie. compiler-, stdlibrary-, or pthread-
issue

What-it-does:
  10 threads race for a job. The main thread supplies the job.
  One of the threads takes the job and processes it.
  This is repeated 10000 times.
  BUT: sometimes the pgm freezes (ie. a deadlock bug happens) --> see below

Compile:
  g++ -Wall -O2 -std=gnu++11 test.cpp -lpthread

Run:
  ./a.out
  repeat multiple times (up to 10 times should be ok for the runtime bug to
show up)

Symptoms of the bug:
  sometimes pgm lands in an endless-loop! ie. deadlock happens --> pgm not
finishing

Test environment:
  - g++ --version
    g++ (Debian 4.9.2-10) 4.9.2

  - uname -a
    Linux my 4.2.0-0.bpo.1-amd64 #1 SMP Debian 4.2.6-3~bpo8+2 (2015-12-14)
x86_64 GNU/Linux

  - dpkg -l | grep -i pthread
    ii libpthread-stubs0-dev:amd64  0.3-4  amd64 pthread stubs not provided by
native libc, development files

See also:
  [1] http://www.cplusplus.com/reference/condition_variable/condition_variable/
  [2] http://en.cppreference.com/w/cpp/thread/condition_variable
*/

#include <iostream>
#include <atomic>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <unistd.h>
#include <vector>

using namespace std;

mutex        mtx;
condition_variable cv;
atomic<bool> fReady;      // init done in main
atomic<bool> fQuit;       // init done in main
atomic<bool> fThreadsOk;  // init done in main

void threadfunc(int id)
  {
/*
Any thread that intends to wait on condition_variable has to acquire a
unique_lock<mutex> first.
The wait operations atomically release the mutex and suspend the execution of
the thread.
When the condition variable is notified, the thread is awakened, and the mutex
is reacquired [2].
*/

    while (!fQuit)
      {
        // wait for fReady:
        unique_lock<mutex> lck(mtx);
        fThreadsOk = true;
        cv.wait(lck);   // unlocks lck, and waits for cv be signalled; then
autom. reacquires lck
        if (fQuit) break;
        if (!fReady) continue;

        // work, ie. process the job:
        cout << "thread " << id << " has grabbed the job\n";
        //...

        // notify parent with fReady=false; wakes up also all the other threads
        fReady = false;
        cv.notify_all();
      }
  }

int main()
  {
    fQuit      = false;
    fReady     = false;
    fThreadsOk = false;

    const size_t N = 10;
    vector<thread> threads;
    for (size_t i = 0; i < N; ++i)
      threads.push_back(thread(threadfunc, i));

    // wait so that at least one thread has done "cv.wait(lck)", see above
    while (!fThreadsOk) sleep(1);

    for (size_t i = 0; i < 10000; ++i)
      {
        cout << N << " threads ready to race: ";

        // notify threads about work to do
        {
        unique_lock<mutex> lck(mtx);
        fReady = true;
        cv.notify_all();

        // wait till job was done
        while (fReady) cv.wait(lck);
        }
      }

    // set fQuit and wake up the threads
    {
    unique_lock<mutex> lck(mtx);
    fQuit = true;
    cv.notify_all();
    }

    // wait till all threads quit:
    for (auto& th : threads) th.join();

    cout << "pgm finished\n";
    return 0;
  }

// end of test.cpp



-- System Information:
Debian Release: 8.2
  APT prefers stable
  APT policy: (500, 'stable')
Architecture: amd64 (x86_64)
Foreign Architectures: i386

Kernel: Linux 4.2.0-0.bpo.1-amd64 (SMP w/4 CPU cores)
Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8)
Shell: /bin/sh linked to /bin/dash
Init: sysvinit (via /sbin/init)

Versions of packages g++-4.9 depends on:
ii  gcc-4.9            4.9.2-10
ii  gcc-4.9-base       4.9.2-10
ii  libc6              2.19-18+deb8u1
ii  libcloog-isl4      0.18.2-1+b2
ii  libgmp10           2:6.0.0+dfsg-6
ii  libisl10           0.12.2-2
ii  libmpc3            1.0.2-1
ii  libmpfr4           3.1.2-2
ii  libstdc++-4.9-dev  4.9.2-10
ii  zlib1g             1:1.2.8.dfsg-2+b1

g++-4.9 recommends no packages.

Versions of packages g++-4.9 suggests:
pn  g++-4.9-multilib    <none>
pn  gcc-4.9-doc         <none>
pn  libstdc++6-4.9-dbg  <none>

-- no debconf information