Multithreaded rendering synchronization issue (double buffering)

have you declared renderThreadID volatile? Otherwise the compiler assumes that the variable doesn't need to be visible outside of the while loop in a single thread, hence in ExecuteCommandList it might determine that there is no use in changing that variable and will optimize it out.

In some APIs, 'waits' are allowed to wake up spuriously (early, without the condition actually being met). In such APIs, they have to be called in a loop that checks the condition.

You don't really show how the main thread uses this ID variable. Do the two threads share it, but pass ownership of it back and forth via those waits/signals, so that only one thread owns it at a time? It might be better to show a simple bit of pseudocode or a diagram of how these two threads are meant to be synchronizing/sharing data.

@Krypt0n volatile is not for multithreading use on multicore PCs; using it for such only guarantees memory ordering bugs.

@Hodgman
no, volatile signals the compiler to make changes visible outside the scope of the current translation unit and runtime. something like

while(!renderThreadID){};

can be optimized into

if(!renderThreadID)
while(true){};

if renderThreadID is not volatile.

@Hodgman
no, volatile signals the compiler to make changes visible outside the scope of the current translation unit and runtime. something like

while(!renderThreadID){};

can be optimized into

if(!renderThreadID)
while(true){};

if renderThreadID is not volatile.

Yeah I know, but it should still never be used to let the compiler know that the variable can be modified by another thread, unless you're on an old single-core PC with no instruction or memory reordering capabilities. Even with that fix, it's still horribly broken.

e.g. Given some code like this, someone might expect that volatile will allow the producer thread to signal the consumer thread, resulting in the consumer spinning for a while and then printing 42.

int data[2] = { -1, -1 }
volatile int index = 0;
//producer thread:
data[0] = 42;
index = 1;
//consumer thread:
while( index == 0 ) { /* spin */ }
printf( "%d", data[0] );

However, the CPU itself (not even the compiler!!) might decide to read the value of data[0] before it reads the value of index, leading this to print -1 instead of 42 as expected. Likewise, the CPU might decide to write index=1 to memory before it writes data[0]=42 to memory, leading to the same result of -1 being printed. It might print 42, but that's down to chance, not correct code.
Even if the compiler does produce the loads and stores in the right order (which it's not actually bound to, unless data is also volatile), CPUs themselves are allowed to reorder loads and stores as long as the single-threaded behavior of the program would not be affected. The CPU does not know that you've marked a variable as volatile or not. You need to explicitly tell the CPU that it's not allowed to reorder memory accesses with a memory fence instruction (which the compiler will emit when using atomics, critical sections, or any kind of actual synchronization primitive). If you use the volatile keyword in multi-threaded code, you have a bug.

(which the compiler will emit when using atomics, critical sections, or any kind of actual synchronization primitive)

that's not correct. it depends on the implementation of the synchronization primitive. e.g. there are processor architectures which require explicit cache flushes, on these the atomic implementations commonly don't enforce a flush or memory sync beyond the actual atomic, otherwise simple spins would become insanely expensive.
Hence, don't rely on this behavior, it's probably just the implementation you're used to.
as an example: std::atomic allows you to specify memory ordering: http://en.cppreference.com/w/cpp/atomic/memory_order
and you obviously don't need to pay the price for it, if you don't need it, it's not enforced. therefore there is no generic rule that synchronization primitives enforce memory visibility.

@Hodgman
no, volatile signals the compiler to make changes visible outside the scope of the current translation unit and runtime. something like

while(!renderThreadID){};

can be optimized into

if(!renderThreadID)while(true){};

if renderThreadID is not volatile.
 

Yeah I know, but it should still never be used to let the compiler know that the variable can be modified by another thread, unless you're on an old single-core PC with no instruction or memory reordering capabilities. Even with that fix, it's still horribly broken.

don't make these "always true" assumptions. if you know your architecture, and you know what you are doing, then it makes no sense to take the more expensive route just for the sake of ideological correctness. There is fully valid software that uses volatile for communication, it's not just for "cores", it can be for system wide data exchange.
(Don't read that I say "all you need is volatile", that's not what I imply! ;) )

e.g. Given some code like this, someone might expect that volatile will allow the producer thread to signal the consumer thread, resulting in the consumer spinning for a while and then printing 42.

int data[2] = { -1, -1 }volatile int index = 0;//producer thread:data[0] = 42;index = 1;//consumer thread:while( index == 0 ) { /* spin */ }printf( "%d", data[0] );

However, the CPU itself (not even the compiler!!) might decide to read the value of data[0] before it reads the value of index, leading this to print -1 instead of 42 as expected. Likewise, the CPU might decide to write index=1 to memory before it writes data[0]=42 to memory, leading to the same result of -1 being printed. It might print 42, but that's down to chance, not correct code.

hypothetically possible, practically he runs windows, DX11, on an x86 CPU. There is just one case where x86 reorder memory operations and your example is not covering it.
with one producer, one consumer, on x86, you'll get away without atomics.

yes, atomics + barriers are the "safe route", but that's what he has already verified, that's why he was asking for guidance, hence trying to use volatile might hint that his compiler was optimizng loops. your suggestion about sporadic awakening is just as valid to try.

Well basically all the main thread does with renderThreadID is use it as the subscript to access the correct one of the two buffers (aka the one that is not being worked on by the render thread) like so commandList[renderThreadID][size] I tried making it volatile as you suggested but that didnt help. Also I believe I'm already handling the spurious wakeup condition:

class Event
{
public:
		Event() : flag(false) {}

		void Set()
		{
				flag = true;
				condition.notify_all();
		}
		void Reset()
		{
				flag = false;
				condition.notify_all();
		}
		void Wait()
		{
				std::unique_lock lk(m);
				while (!condition.wait_for(lk, std::chrono::milliseconds(0), [this]() { return flag; }))
				{
						if (flag) // avoid spurious wakeup
								break;
				}
		}
		void Wait(const long milliseconds)
		{
				std::unique_lock lk(m);
				condition.wait_for(lk, std::chrono::milliseconds(milliseconds), [this]() { return flag; });				
		}

private:
		mutable std::mutex m;
		mutable std::condition_variable condition;
		bool flag;
};


#endif

The only synchronization between the threads is the wait/signalling. If that works correctly there should be no need for a barrier around that renderThread variable or not ? Or perhaps I need to rethink this more...

have you declared renderThreadID volatile?

long explanation

Everything you say is perfectly correct under those very narrow assumptions (Windows X86 system, and MSVC compiler), but I guess what Hodgman tried to point out was that using a std::atomic and doing a store(...std::memory_order_relaxed) is the same thing and none more expensive (will be an ordinary store on X86 with very, very little impact on the compiler's ability to reorder instructions), but it is 100% reliable and portable (and... formally correct).

In some APIs, 'waits' are allowed to wake up spuriously (early, without the condition actually being met).

Unlikely, Windows tends to oversleep (well-known) but it rearely over-waits (it's possible, being non-RT, but priority boost makes it magically work 99.9% reliably), and to my knowledge never spuriously wakes, except in one condition that practically never happens. The only situation of which I'm aware of in which this can happen is being in an alertable wait (one of SleepEx(...TRUE), GetQueuedCompletionStatus(), or NtWaitForKeyedEvent(...TRUE)) and during your wait, another thread posts a user-level APC (kernel APCs just run and block your thread again without leaving a trace) or calls NtAlertThread(). So, unless you build your event class around a keyed event or a critical section (which uses a keyed event) and at the same time have some code in another thread which does one of the above, that shouldn't happen. Since you have to deliberately do something very specific, you would likely know if that was the case. I don't know how MSVC imlements its condition variables, but might as well be that there's a KEV in there. Though why a spurious wake should cause a deadlock is beyond my understanding...

while (!condition.wait_for(lk, std::chrono::milliseconds(0), [this]() { return flag; }))

Is this deliberate?

That's not likely to be the cause of your problem, but you do know that this is not the same as calling wait()? On the contrary, given a zero timeout you are never waiting, this is busy spinning.

have you declared renderThreadID volatile?

 

long explanation

Everything you say is perfectly correct under those very narrow assumptions (Windows X86 system, and MSVC compiler), but I guess what Hodgman

I agreed with him if he talks hypothetically, and pointed out my reply was just a poke for the narrow case the topic starter has. (as nobody even tried to help for 2 weeks apparently). if it doesn't help, it's fine, but it gets the topic going and everybody gives a random shot and we solve it together. I never intended to claim I'm a master in remote-crystal-ball-debugging :)

tried to point out was that using a std::atomic and doing a store(...std::memory_order_relaxed) is the same thing and none more expensive (will be an ordinary store on X86 with very, very little impact on the compiler's ability to reorder instructions), but it is 100% reliable and portable (and... formally correct).

was not clear to me that he was talking about std::atomic, he seem to talk about any implementation of atomics (or synchronization primitives in general).
like he pointed out, it's not just about compiler reordering of instructions, it's about memory ordering of the hardware. yes, even on x86 you might need that, depending on the case. relaxed might be not enough.

relaxed might be not enough

That is absolutely true as well. I was just saying relaxed because that's what using volatile more or less translates to. A guaranteed, atomic memory write, with no other guarantees. In the X86 world, that's a plain normal write to memory (...that always happens and is never optimized out).

To be strictly correct, you will usually have to use acquire and release in such a producer-consumer-like scenario where one thread waits on another having completed something, to be sure that non-atomic writes prior to the release are not reordered such that they won't be consistently visible after the atomic acquire. Which, again, translates to plain normal instructions -- at least on X86 -- only just the compiler is not allowed to reorder stores (which it probably doesn't do anyway in this case, so the impact is usually very small if not zero).

That being said, using any of the "heavyweight" synchronization mechanisms (including e.g. condition_variable::wait) guarantees sequential consistency, which is the most strict guarantee... so actually you should be able to get away without any other memory ordering guarantees (whether formally correct or not).

Sidenote: Since I'm not using condition variables (their mode of operation with writing to not-owned data protected by a mutex instead of exclusively writing owned data, and tampering on that mutex behind your back within the wait function always struck me as contorted and perverse), I've read through the specs to familiarize myself with them again and understand exactly what happens, and when.

Turns out it unlocks the mutex while blocking, and re-acquires it while unblocking. Which may mean that if another thread is signalling the condition variable again while your are in the process of being unblocked, this may in fact block you (temporarily). Which I guess is OK because that's how condition_variable works. However, if two threads are -- correctly and legitimately -- waking up, they will also lock out each other (for no good reason, really), and if they have a dependency, you will have a deadlock. But maybe this constellation counts as "using condition variable wrong", I'm not sure.

your mutex does no work. you miss some guarding (although I don't know if that's already the issue)

class Event{public:		Event() : flag(false) {}		void Set()		{                                {                                std::lock_guard lk(m);  //<---				flag = true;                                }				condition.notify_all();		}		void Reset()		{                                {                                std::lock_guard lk(m);  //<---				flag = false;                                }				condition.notify_all();		}		void Wait()		{				std::unique_lock lk(m);				while (!condition.wait_for(lk, std::chrono::milliseconds(0), [this]() { return flag; }))				{						if (flag) // avoid spurious wakeup								break;				}		}		void Wait(const long milliseconds)		{				std::unique_lock lk(m);				condition.wait_for(lk, std::chrono::milliseconds(milliseconds), [this]() { return flag; });						}private:		mutable std::mutex m;		mutable std::condition_variable condition;		bool flag;};#endif

Which, again, translates to plain normal instructions -- at least on X86 -- only just the compiler is not allowed to reorder stores (which it probably doesn't do anyway in this case, so the impact is usually very small if not zero).

sorry, but that's again not (strictly) correct. that's exactly what I've tried to point out. it's not about "only just the compiler is not allowed to reorder stores", x86 also needs a memory barrier to avoid reordering on the hardware load/store queue. two threads running something like

mov [threadID],0
mov eax,[threadID^1]

_both_ might end up with eax!=0, on x86.
(yes, that's pseudo code, not valid assembler :) )

 

while (!condition.wait_for(lk, std::chrono::milliseconds(0), [this]() { return flag; }))

Is this deliberate?

That's not likely to be the cause of your problem, but you do know that this is not the same as calling wait()?  On the  contrary, given a zero timeout you are never waiting, this is busy spinning.

 

I believe that is for avoiding the spurious wakeup case.
So if the two threads blocking each other is the issue (which I believe it is) how would I avoid them doing it ? Some kind of restriction on who goes first ? I thought the order of set and wait would be given by the mutex locks.

@Krypt0n I figured there needs to be a lock before setting and resetting the flag as well however this implementation seemed to be the consensus of what you find on the internet for some reason...still does not fix the original issue.

Also not sure if it helps you figure it out but if I set a wait time in the condition to something like 20ms it runs, however slow (obviously).

update:
Basically what I can tell you from debugging is that when I run it in debug and pause where it hangs it will stop here:
MAIN THREAD:

		this->renderer->RenderDoneCondition().Wait();
		this->renderer->RenderCommandsReadyCondition().Set();
		this->renderer->BufferSwappedCondition().Wait(); // Hangs here

RENDER THREAD:

				// Wait for [MAINTHREAD] to provide us with command list data
				bufferSwappedCondition.Reset();
				renderDoneCondition.Set();
				renderCommandsReadyCondition.Wait(); // hangs here

				renderDoneCondition.Reset(); 
				renderCommandsReadyCondition.Reset();

				// Swap buffer IDs
				renderThreadID = !renderThreadID;

				// Notify [MAINTHREAD] that the buffer was swapped, so we can generate new commands in parallel
				bufferSwappedCondition.Set();

With the flag states being:
renderCommandsReadyCondition = false
bufferSwappedCondition = false
renderDoneCondition = true

So both threads use renderThreadID concurrently to write into their own buffers, but then both have to sync up to flip the value of renderThreadID or very bad things will happen, right?
And the method for doing this is:

Main loop:
//Use renderThreadID
Main --> RenderDoneCondition.Wait()
Main --> RenderCommandsReadyCondition.Set()
Main --> BufferSwappedCondition.Wait()

Render loop:
//Use renderThreadID
Render --> BufferSwappedCondition.Reset()
Render --> RenderDoneCondition.Set()
Render --> RenderCommandsReadyCondition.Wait()
Render --> RenderDoneCondition.Reset()
Render --> RenderCommandsReadyCondition.Reset()
Render --> renderThreadID = !renderThreadID
Render --> BufferSwappedCondition.Set()

Personally, I've always hated these resettable events because I find it really hard to reason whether the logic is ever correct or not, and easily identify the weird edge cases where it's wrong (which is probably what's happening for you here :( )

Ideally they interleave like this and everything is fine:

Main   --> RenderDoneCondition.Wait() // main blocks
Render --> BufferSwappedCondition.Reset()
Render --> RenderDoneCondition.Set() // unblocks main
Render --> RenderCommandsReadyCondition.Wait() // render blocks
Main   --> RenderCommandsReadyCondition.Set() // unblocks render
Main   --> BufferSwappedCondition.Wait() // main blocks
Render --> RenderDoneCondition.Reset()
Render --> RenderCommandsReadyCondition.Reset()
Render --> renderThreadID = !renderThreadID
Render --> BufferSwappedCondition.Set() //unblocks main
Main & Render --> Use renderThreadID 

But if you unroll a few frames worth of these commands, you can interleave them in different ways...
If you're unlucky and render thread runs fast while the main thread has a little hicup, they can interleave like this:

Main1   --> RenderDoneCondition.Wait() // main blocks
Render1 --> BufferSwappedCondition.Reset()
Render1 --> RenderDoneCondition.Set() // unblocks main
Render1 --> RenderCommandsReadyCondition.Wait() // render blocks
Main1   --> RenderCommandsReadyCondition.Set() // unblocks render
Render1 --> RenderDoneCondition.Reset()
Render1 --> RenderCommandsReadyCondition.Reset()
Render1 --> renderThreadID = !renderThreadID
Render1 --> BufferSwappedCondition.Set()
Render2 --> BufferSwappedCondition.Reset()
Render2 --> RenderDoneCondition.Set()
Render2 --> RenderCommandsReadyCondition.Wait() // render blocks
Main1   --> BufferSwappedCondition.Wait() // main blocks
DEADLOCK

As I hate the things, I would recommend using something dumber and simpler, such as a status structure protected by a lock/mutex/critical-section, such as:

struct Status {
 Lock l;
 int mainCount;
 int renderCount;
 int index;
 int MainDone()
 {
  //increment main counter, and wait while we're ahead of the renderer. Return the value of index.
  l.Lock();
  ++mainCount;
  l.Unlock();
  bool canContinue;
  int newIndex;
  do
  {
   _mm_pause();//todo other busy waiting technique...
   l.Lock();
   canContinue = (mainCount == renderCount);
   newIndex = index;
   l.Unlock();
  } while(!canContinue);
  return newIndex;
 }
 int RenderDone()
 {
  //wait until the main thread is waiting on the render thread
  l.Lock();
  while(mainCount != renderCount+1)
  {
   l.Unlock();
   _mm_pause();//todo other busy waiting technique...
   l.Lock();
  }
  //flip the index (returning the new value), and increment the render counter so that the main thread can unblock
  ++renderCount;
  int newIndex = (index = !index);
  l.Unlock();
  return newIndex;
 }
};

and then optimize it later if it's an issue. You can actually pack those three integers into a single 32bit atomic and use a compare-and-swap loop to implement that structure/algorithm :)

That's obviously untested so I hope I don't have a similar bug :o

but I guess what Hodgman tried to point out was that using a std::atomic and doing a store(...std::memory_order_relaxed) is the same thing and none more expensive (will be an ordinary store on X86 with very, very little impact on the compiler's ability to reorder instructions), but it is 100% reliable and portable (and... formally correct).

Yeah that's what I was getting at -- the "right way" works everywhere and has the same cost as the simple way when on a platform where the simple way is enough.

I tried your suggested solution and it seems to work nicely but the only thing that I can't quite comprehend is the way those mutex locks work. How can you be sure that the lock() call in RenderDone isn't called at the same time as the lock() in MainDone, or what if one locks it and the other also attempts to lock it before it has been unlocked again. Is that not an issue ?
Also mainCount and renderCount are incremented but never reset I understand this might still work even after an overflow but still seems kind of like undefined behavior...just making sure that's 'as designed' ?