3
\$\begingroup\$

I have a requirement that is summarized below.

void update()
{
  |   |   |   |
  |   |   |   |
  |   |   |   |
 \|  \|  \|  \|
  =============
      meat           <--- Only one thread must execute here, the rest should skip it.
  =============
  |   |   |   |  <--- Other threads wait here until the "first" thread is done w/ "meat"
  |   |   |   |
  |   |   |   |
  |/  |/  |/  |/
}

From an outsider perspective, "meat" should be executed just once (by the first thread that encounters it)

This post is similar but differs in that it also requires other threads to execute the meat code block one at a time.

// testExecutive.cpp
#include <atomic>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <thread>

struct Target {
  int nhits = 0;
  inline void hit() { ++nhits; }
};

struct Executive {
  Executive() = delete;
  Executive(int _Id, Target &_Tgt) : m_Id(_Id), m_Ready(false), m_Tgt(_Tgt) {}
  void update() {
    { // only one thread can execute this
      std::scoped_lock<std::mutex> lk(m_Mtx);
      // std::cout << "++Acquired lk " << m_Id << " | tid: " <<
      // std::this_thread::get_id() << "++\n";
      if (!m_Ready.load()) {
        // std::cout << "==Updating" << m_Id << " | tid: " <<
        // std::this_thread::get_id() << "==\n";
        m_Ready.store(true);
        m_Tgt.hit();
        m_Cv.notify_all();
      }
      // std::cout << "++Releasing lk " << m_Id << " | tid: " <<
      // std::this_thread::get_id() << "++\n";
    }

    // the rest should wait here
    std::mutex wait_mtx;
    std::unique_lock<std::mutex> lk(wait_mtx);
    m_Cv.wait(lk, [&]() -> bool { return m_Ready.load(); });
  }
  inline void reset() { m_Ready.store(false); }

private:
  int m_Id;
  Target &m_Tgt;
  std::condition_variable m_Cv;
  std::mutex m_Mtx;
  std::atomic_bool m_Ready;
};

int main(int argc, char *argv[]) {
  int n(2);
  if (argc >= 2) {
    n = atoi(argv[1]);
  }
  Target tgt;
  Executive e(1, tgt);
  auto updFn = [&e]() { e.update(); };

  // update same executive from 3 threads. Repeat n times.
  int i(n);
  while (i > 0) {
    e.reset();
    {
      std::thread t1(updFn), t2(updFn), t3(updFn);
      t1.join();
      t2.join();
      t3.join();
    }
    --i;
  }
  std::cout << (n == tgt.nhits ? "[OK]" : "[ERR]") << " Updates: " << n << " | "
            << "Hits: " << tgt.nhits << "\n";
  return 0;
}

I setup a simple method to verify that exactly one out of three threads executes the desired code. The method hit() is called in Executive::Update. Compile and test like so.

jaswant@HAL9000:~$ g++ testExecutive.cpp -lpthread --std=c++17
jaswant@HAL9000:~$ ./a.out 2
[OK] Updates: 2 | Hits: 2
jaswant@HAL9000:~$ ./a.out 100
[OK] Updates: 100 | Hits: 100
jaswant@HAL9000:~$ ./a.out 2
[OK] Updates: 2 | Hits: 2
jaswant@HAL9000:~$ ./a.out 4
[OK] Updates: 4 | Hits: 4
jaswant@HAL9000:~$ ./a.out 8
[OK] Updates: 8 | Hits: 8
jaswant@HAL9000:~$ ./a.out 16
[OK] Updates: 16 | Hits: 16
jaswant@HAL9000:~$ ./a.out 256
[OK] Updates: 256 | Hits: 256
jaswant@HAL9000:~$ ./a.out 1024
[OK] Updates: 1024 | Hits: 1024
jaswant@HAL9000:~$ ./a.out 8192
[OK] Updates: 8192 | Hits: 8192
jaswant@HAL9000:~$ ./a.out 100000
[OK] Updates: 100000 | Hits: 100000

So, it works. Can anyone please point out bad usage of mutex/condition variables/locks and perhaps a way to do this w/o an atomic variable in the predicate?

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Your problem is exactly std::once_flag; see quuxplusone.github.io/blog/2020/10/23/once-flag \$\endgroup\$ – Quuxplusone Jan 11 at 18:47
  • \$\begingroup\$ Just to be clear, can the first thread execute the "meat" before the others have reached it, or do all threads really have to wait to arrive there before the "meat" can be executed? And if the latter, does it really matter which thread executes it? \$\endgroup\$ – G. Sliepen Jan 12 at 17:07
  • \$\begingroup\$ @G.Sliepen. It is the former. Also, it doesn't matter which thread executes it. All that matters is for an instance of the executive; unless reset, "meat" should execute only once. The requirement is similar to #pragma omp single w/o the nowait clause. \$\endgroup\$ – jaswantp Jan 12 at 17:10
  • 1
    \$\begingroup\$ Ok, then it might very well be that std::once_flag is indeed all you need. \$\endgroup\$ – G. Sliepen Jan 12 at 17:12
  • 1
    \$\begingroup\$ Welcome to Code Review. I have rolled back your latest edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Jan 13 at 6:45
4
\$\begingroup\$

Use std::once_flag

The std::once_flag class basically does what you want. However, there is no way nice way to reset it, except by using a trick like placement new, or by allocating a flag dynamically, and using a std::unique_ptr to point to it for example. As indi mentioned, it's not really "once" anymore then, but it does work for your specific case. Here is a drop-in replacement for your struct Executive:

struct Executive {
  Executive(int _Id, Target &_Tgt) : m_Id(_Id), m_Tgt(_Tgt) {}
  void update() {
        std::call_once(flag, [this]{ m_Tgt.hit(); });
  }
  void reset() {
    flag.~once_flag();
    new (&flag) std::once_flag;
  }

private:
  int m_Id;
  Target &m_Tgt;
  std::once_flag flag;
};

No need to write inline

If you include the full definition of a member function in a class or struct definition, you don't need to explicitly use the inline specifier, as it will implicitly be an inline function.

Write idiomatic code

There are a few things in your code that are not incorrect in any way, but are a rather unusual way to write things. For example, when declaring an int and initializing it, I would expect int n = 2 or int n{2}, but not int n(2).

Also, when repeating something a number of times, use a for-loop, like so:

for (int i = 0; i < n; ++i) {
    e.reset();
    ...
}

This completely describes how often the loop is run in a single line, which makes it easier to read.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Eeeeh… 😬. If you’re going to do this, you should at least call the destructor before re-constructing in place. Even then, this strikes me as at least immoral, if not outright wrong. It will (probably!) “work” for the program given, because each thread is started after the reset, and then quits without reset() ever being called again. But if you start threads then call reset()… 🤷🏼. I see no promises that “reconstructing” a once_flag will be properly propagated across threads without at least some manual synchronization like fences (which kinda defeats the purpose). \$\endgroup\$ – indi Jan 13 at 2:56
  • 1
    \$\begingroup\$ And by the way, this applies even if you try to do something like dynamically allocate the once_flag, then delete and re-new it in update(). It’s not the placement new that’s fishy here, it’s constructing (or re-constructing) the once_flag after the threads that will be waiting on it. \$\endgroup\$ – indi Jan 13 at 2:57
  • \$\begingroup\$ @indi, "But if you start threads then call reset()", this is guaranteed to never occur in my use case. reset is called only when all threads are done with update. \$\endgroup\$ – jaswantp Jan 13 at 6:04
3
\$\begingroup\$

Don’t overthink the plumbing

With no disrespect to Mr. O’Dwyer, I think he missed something key going on here. std::call_once is the best tool for the job… if you’re really only calling some code once.

But your code includes a reset() function. That immediately invalidates the whole idea of std::call_once (and, by extension, std::once_flag). call_once means “call once”. Not “call once-at-a-time”… which is really what you’re looking for.

With respect to the fairy tale metaphor, call_once is call_once… not call_once_upon_a_time. If your situation matches O’Dwyer’s metaphor, where a single knight gets to the princess, and then it’s all over, they get married, there’s a happily-ever-after… that’s call_once. But if your situation allows for the marriage to end in divorce after a while, and then the princess goes back up on the glass hill to give another group of knights a shot… that’s not call_once. That’s something else.

So what is the right pattern here?

Well, your situation is actually the classic double-checked problem. You don’t need double-checked locking; that’s just an optimization. You just need locking. Simple, basic locking. No tricks. Nothing complicated.

I know all the cool kids are using condition variables these days, but you don’t need that here either. Alls you need is a mutex and a flag. Heck, you can even get away with the pre-C++20 atomic_flag:

struct Executive {
    Executive(int id, Target& tgt) :
        m_Id{id},
        m_Tgt{tgt}
    {
        // need this before C++20
        m_done.clear(); // or .clear(std::memory_order_release)
    }

    void update() {
    {
        auto lock = std::scoped_lock(m_Mtx);
        
        if (not m_Done.test_and_set()) // or .test_and_set(std::memory_order_acq_rel)
        {
            m_Tgt.hit();
        }
    }

    void reset()
    {
        m_Done.clear(); // or .clear(std::memory_order_release)
    }

private:
  int m_Id;
  Target& m_Tgt;
  std::mutex m_Mtx;
  std::atomic_flag m_Done;
};

Yup. That’s literally it. Just a lock and a flag.

To understand how it works: If you have a bunch of threads that want to run the “meat” function, every one of them is going to stop cold at the lock… except one. That one thread will set the flag to true, and then run the target function. When it’s done, it will release the lock… and then every other thread will start running… they will all see the flag is already set, so they will skip running the target function. Thus, the target function only gets run once.

Simple.

Resetting is also simple. Just clear the flag.

If you want to use the classic double-checked locking trick, that’s fine too… you just can’t use the pre-C++20 atomic_flag anymore; you’d have to use atomic<bool>. (But from C++20 you could still use atomic_flag!)

Okay… everything’s not that simple….

Tolerating failure.

One thing that once_flag does that’s really handy is take care of the case where the target function can fail. But that’s trivial to add:

void update() {
{
    auto lock = std::scoped_lock(m_Mtx);
    
    if (not m_Done.test_and_set())
    {
        try
        {
            m_Tgt.hit();
        }
        catch (...)
        {
            m_Done.clear();

            // What to do now? Depends what you want.
            //
            // You could re-throw the exception, but you'd need to catch it
            // somehow or it'll just end up calling std::terminate().
            //
            // If you want to allow retries, you could simply wrap the whole
            // thing in a loop. (But be smart about it. You only want to redo
            // the loop if you ended up in this catch block - that is, if
            // you tried and failed. If you tried and succeeded, or if some
            // other thread succeeded and set m_Done, you don't want to loop.)
        }
    }
}

Again, simple. Don’t overthink the plumbing!

The big picture; or, okay, maybe overthink the plumbing a little

Alright, so your Executive class basically manages a critical section so that it only gets executed once, and it allows resets. Now, if you’re very careful to ensure that you only call reset() when no thread is executing update(), then you’ll have no problems.

But if you’re not careful… well consider this situation:

  1. You create two threads, t1 and t2 to run foo() once.
  2. t1 acquires the lock, then goes to sleep.
  3. t2 tries to acquire the lock, but t1 owns it, so it blocks, and goes to sleep.
  4. t1 wakes up, and then runs through to the end of update()—calling foo() once—then releases the lock.
  5. Your main thread sees foo() has been called, and so figures the job is done. It calls reset() (I don’t know why for, maybe in anticipation of needing foo() called again in the future?).
  6. t2 then wakes up, acquires the lock, and then sees the flag is clear… so it sets the flag and calls foo().

Thus, foo() ended up being called twice.

This is not an impossible problem to solve… it just can’t be solved from within update(), or even Executive, because it requires knowing how many threads are trying to call update(). If you know how many threads are involved, there are several ways you can make sure that they all finish update() (so you know when it’s safe to call reset()). You can use an atomic<int> as a counter, or a barrier… you have options.

Or maybe you won’t actually need anything at all, because (as with your current main()) the problem never arises. I’m not actually suggesting you go ahead and implement something to guard against this—quite the opposite in fact—I’m just warning you to be aware.

In fact, I would suggest giving careful thought as to whether you need reset() capability at all. As you can see from this section, it is not a trivial addition; it adds significant cognitive complexity. And you don’t really need it, at least not in the code you have written. You just need to rethink things. Instead of:

Target tgt;
Executive e(1, tgt);
auto updFn = [&e]() { e.update(); };

int i(n);
while (i > 0) {
  e.reset();
  {
    std::thread t1(updFn), t2(updFn), t3(updFn);
    t1.join();
    t2.join();
    t3.join();
  }
  --i;
}

just do:

Target tgt;

int i(n);
while (i > 0) {
  Executive e(1, tgt);
  auto updFn = [&e]() { e.update(); };

  {
    std::thread t1(updFn), t2(updFn), t3(updFn);
    t1.join();
    t2.join();
    t3.join();
  }

  --i;
}

If you don’t really need reset()… I’d suggest dropping it. No sense inviting nasty race condition bugs unnecessarily.

And if you drop reset(), and you really only need the target function called onceever, in the entire program (not just once-at-a-time)—and you ensure that the executive is set up before the threads… then yeah, Quuxplusone and G. Sliepen are right, you might be able to get away with using std::once_flag.

Code review

struct Target {
  int nhits = 0;
  inline void hit() { ++nhits; }
};

G. Sliepen already mentioned that the inline is pointless here (and everywhere, pretty much; don’t use inline just because you think it will make you code faster (you’ll usually be wrong); don’t use inline unless you know you need to).

But the real problem here is that you are using this class as shared, mutable data across multiple threads… and you have not a single whiff of synchronization anywhere. I presume you’re running you code on an x86, probably x86-64. Well, on that hardware you’re safe because ints will be naturally atomic (mooooooost of the time), and everything sequentially consistent (ish!). But if you switched to less beginner-friendly hardware, you may find some surprises.

++nhits is not a trivial operation. It has to load nhits into a register (we’ll presume, for simplicity), increment the value, then store the result back into nhits. If all this is atomic, no problems. Buuuuut… if thread 1 loads nhits, then stalls… then thread 2 loads nhits, then stalls… then thread 1 increments and stores the result… then thread 2 increments and stores the results… you might be expecting the final result of two threads incrementing nhits to be 2… but it will be 1!

And that is just the tip of the iceberg. The other issue here is “tearing”. This occurs when the processor can’t load/store the entire value of nhits in a single step, so it has to do multiple loads/stores. For example, imagine you have a 16-bit processor and nhits is a 16-bit int… which happens to be misaligned in memory—it’s at address 0x1001 rather than 0x1000 or 0x1002. So the processor has to do two loads to read nhits: first it loads the 16 bits starting at 0x1000, and shifts that right by 8 bits… then it loads the 16 bits starting at 0x1002 and ANDs that with 0x00FF… then it ORs the two results together to get the actual value of nhits. THEN it does the increment, and then goes through the whole dance in reverse to write the value back to memory address 0x1001. At ANY STEP IN ALL OF THAT, the thread may be swapped out, and another thread starts running. If nhits gets loaded/stored halfway in one thread while another thread is loading/storing it, you could end up with a situation where part of nhits was written by one thread and another part of it was written by another. In other words, you could end up with gibberish.

The bottom line is this: Target is shared, mutable data. Shared, mutable data MUST be synchronized somehow. You can’t just go commando.

You don’t need to synchronize it within the class. You could use external synchronization. But you must use some synchronization. Because right now, you have a race condition; you have UB.

Executive() = delete;

You don’t need this; don’t write code that serves no purpose, it just becomes a maintenance burden.

Executive(int _Id, Target &_Tgt) : m_Id(_Id), m_Ready(false), m_Tgt(_Tgt) {}

Identifiers that begin with an underscore followed by an uppercase letter are illegal. Besides, you don’t need to tag function arguments. The point of tagging variables with things like an underscore, or m_, is because they’re “global-ish”; that is, they are used in scopes that they aren’t declared in. The tag signals to you “I know you can’t see where this variable is defined; don’t panic, it’s a data member of this class (if it has m_, for example)”. But with function arguments, you can see where they’re defined, and they don’t extend beyond the function scope. So tagging them is pointless.

Just do:

Executive(int id, Target& tgt) : m_Id(id), m_Ready(false), m_Tgt(tgt) {}

Also, you have mixed up the order of variables; the order here in the initializer list is not the same as declared in the class. That’s unwise. You should have got a warning. You do have warnings turned on, don’t you?

Now in update():

std::scoped_lock<std::mutex> lk(m_Mtx);

Since you’re using C++17, prefer to use template argument deduction for things like this:

std::scoped_lock lk(m_Mtx);

That decreases the maintenance burden because you’re not repeating the type.

// the rest should wait here
std::mutex wait_mtx;
std::unique_lock<std::mutex> lk(wait_mtx);
m_Cv.wait(lk, [&]() -> bool { return m_Ready.load(); });

This doesn’t do what I think you think it does. It creates a local mutex—so it will be a different mutex in each thread—so all three threads own their own wait_mtx. The reason this… appears… to work is because you then have all three mutexes wait on the same condition variable and condition. I’ll be honest, I’m not even sure it’s legal for a condition variable to work with three different mutexes. But at any rate, they’re all waiting on an atomic variable, so… I guess it shakes out somehow.

And finally, in main():

int i(n);
while (i > 0) {
  e.reset();
  {
    std::thread t1(updFn), t2(updFn), t3(updFn);
    t1.join();
    t2.join();
    t3.join();
  }
  --i;
}

This is… messy… for a lot of reasons. G. Sliepen already mentioned some. I’ll go further.

If you’re going to make x number of threads, it makes more sense to put them all in a container:

for (auto i = 0; i < num_repeats; ++i)
{
    auto threads = std::vector<std::thread>(3); // or std::array<std::thread, 3>{}
    std::generate(threads.begin(), threads.end(), [] { return std::thread{func}; });

    std::for_each(threads.begin(), threads.end(), [](auto&& t) { t.join(); });
}

Even better, as of C++20 you should prefer to use std::jthread, which auto-joins:

for (auto i = 0; i < num_repeats; ++i)
{
    auto threads = std::vector<std::jthread>(3);
    std::ranges::generate(threads, [] { return std::thread{func}; });

    // all threads run then auto-join
}

This is not just a matter of style. Doing it this way allows you to trivially adjust the number of threads:

for (auto i = 0; i < num_repeats; ++i)
{
    auto threads = std::vector<std::jthread>(num_threads);
    std::ranges::generate(threads, [] { return std::thread{func}; });
}
\$\endgroup\$
4
  • \$\begingroup\$ "And if you drop reset(), and you really only need the target function called once—ever, in the entire program (not just once-at-a-time)—and you ensure that the executive is set up before the threads… then yeah, Quuxplusone and G. Sliepen are right, you might be able to get away with using std::once_flag". Partly right. update should run only once per frame. So I think I should use call_once. But thanks for your insights! struct Target was only placed as an example-usage and I did not look to get it reviewed. I'll make a new edit to OP with these suggestions. \$\endgroup\$ – jaswantp Jan 13 at 5:53
  • \$\begingroup\$ “Once-per-frame” ≠ “once”. And unless you’re creating threads every frame (!!!), or doing manual synchronization between reset() and update(), then I see no guarantee that once_flag will work. \$\endgroup\$ – indi Jan 14 at 20:59
  • \$\begingroup\$ I create threads well before the event loop even begins in the application(not recreated each frame!!). I understand the example I put in my question can be miscronstrued to think otherwise. At the end of every frame, an explicit synchronization occurs if any of the threads called update(). Then once_flag is clearly exactly what I need. \$\endgroup\$ – jaswantp Jan 15 at 4:33
  • \$\begingroup\$ Okay, whatever. 🤷🏼 You do you. (For other readers, no, what he’s doing isn’t guaranteed to work, because he’s updating the once_flag after each update(), but there’s no synchronization—like a fence—to propagate that update between threads. The next time the threads get around to checking the once_flag, they may still see the old value—which says “already done”, and the target function will just never get called. Moral of the story: call_once means call ONCE. One time. Ever. In the whole program. Not “once per frame/second/whatever”.) \$\endgroup\$ – indi Jan 15 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.