Endless loop in ImplicitProducer* get_or_add_implicit_producer()

[oviano]

I've been using this nice queue for a while now; one of my usages is as part of a log file writing system. I have a blocking concurrent queue where a thread waits for items before writing them to a text file.

I'm getting a fairly rare situation where about half a dozen or so "producer" threads all need to write at the same time, typically during a shutdown sequence and they all seem to be stuck going round and round in this function.

Not sure how to debug this!

[cameron314]

Can you identify in which loop they are stuck exactly? Can you reproduce in isolation?

[oviano]

		assert(mainHash != nullptr);  // silence clang-tidy and MSVC warnings (hash cannot be null)
		for (auto hash = mainHash; hash != nullptr; hash = hash->prev) {
			// Look for the id in this hash
			auto index = hashedId;
			while (true) {		// Not an infinite loop because at least one slot is free in the hash table
				index &= hash->capacity - 1;

Yes it was basically looping around the outer while(true) { shown above, with index basically going up each iteration and then back to 1 again.

I haven't yet attempted to reproduce in isolation, I will try that tomorrow. I've being chasing a bug in my project where it was entering a stuck/high CPU state and I had left three instances running in the VS debugger and I've literally only caught it this evening for the first time.

[oviano]

Managed to trap it again; it loops endlessly because the condition (probedKey == id) is never met for it to return, and neither is (probedKey == details::invalid_thread_id) for it to break.

details::invalid_thread_id is defined as zero, this is Windows.

The contents of hash->entries[0...31] is mostly with key = 0xFFFFFFFFU but a few valid entries, but none where the key==id.

[cameron314]

Thanks, I'll have a look soon.

[oviano]

In the above last case I encountered it there was actually only one thread looping in this manner. There were no other threads referencing the queue apart from the consumer which was sitting waiting to dequeue.

Not too sure how it works but it seems that either the thread never had a producer hash created or something (another thread?) invalidated it when it shouldn’t have done?

[oviano]

Is it conceivable that the thread exit handler code is clearing down the hash entry after a new thread has started and is already re-using the same thread id/hash?

This seems to happen when threads are stopped and new threads immediately created.

i will disable the thread local stuff and see if the problem automagically goes away….

[oviano]

Apologies for the running commentary - I added some trace to log the thread ID when the thread is subscribed to the thread exit listener, and when the exit handler is called.

What I am finding is that the threads that are stuck in this loop were never seemingly given a producer.

What seems to have happened is that all the previous threads that were stopped earlier have left their producers in the reusable (invalid_thread_id2) state, and so there is never an available empty one (invalid_thread_id) to allow the loop to break.

Does that make sense as an explanation?

[cameron314]

Thanks for looking into this. That makes sense, and is looking increasingly like a bug! I'll take a look at lunch.

[oviano]

It's possibly because I'm using it in a way that is less conventional, i.e. as part of a logging system, where it's normal for threads that come and go during execution to want to write logging items to the queue.

Maybe that's different from the envisaged use of long-running threads in a more stable producer -> consumer model.

[cameron314]

Nah, it seems to be a legitimate bug. I'll try to work out a fix, but in the meantime you can comment out the define of MOODYCAMEL_CPP11_THREAD_LOCAL_SUPPORTED in the header.

Thanks for finding this!

[cameron314]

The implicit producer hash table should always have a load factor of no more than 75%. The infinite loop you see indicates it reached 100%.

invalid_thread_id is used to indicate an empty slot, and invalid_thread_id2 is used as a tombstone for a removed value (and may be later overwritten similar to an empty slot). The count is not decremented when a tombstone is written, so there should always be at least one truly free slot in the hash at all times, preventing that infinite loop.

However, the count was also not being incremented when a free (not reused!) slot was taken for a reused producer, which ultimately resulted in the count not reflecting the reality of the actual hash entries, causing it to fill up to 100% capacity in pathological cases. This should now be fixed.

I also fixed an (unlikely) race during insertion (and replacement with the tombstone during deletion) where stale keys could be read, causing the loop to iterate past a usable value (during insertion) or overwrite a valid value (during deletion). This race could lead to a similar violation of hash invariants.