concurrent_queue::unsafe_size thread safety

[andysem]

Hi,

The comments say thatconcurrent_queue::unsafe_size() method is not thread-safe, but I'd like to know what this means exactly. Is it going to crash or corrupt memory if called concurrently with push/pop? Or is the result of this function possibly inaccurate (but close to the actual length of the queue)? The docs don't state this explicitly.

In my application, I don't need a precise size of the queue, but I need an estimate that is close to the actual value. The primary use of this information is diagnostical.

[Alexey-Kukanov]

Here is the current implementation of the method:

[cpp]template
size_t concurrent_queue_base_v3::internal_size() const {
    concurrent_queue_rep& r = *my_rep;
    ticket hc = r.head_counter;
    size_t nie = r.n_invalid_entries;
    ticket tc = r.tail_counter;
    ptrdiff_t sz = tc-hc-nie;
    return sz<0 ? 0 :  size_t(sz);
}
[/cpp]

It reads three atomic variables and does some simple math. So it does not have any undesirable side effects, as far as I can tell. But the result is indeed inaccurate, and we cannot predict how accurate it is.At the very least, it depends on the number of items in the queue and the number of threads concurrently working with it.

[Dmitry_Vyukov]

Since the counters are monotonic, you can make the operation thread-safe w/o imposing any significant costs. The idea is to grab a consistent snapshot of the 3 variables (memory fences are omitted):

[cpp]size_t concurrent_queue_base_v3::internal_size() const
{  
	concurrent_queue_rep& r = *my_rep;  
	ticket hc = r.head_counter;  
	size_t nie = r.n_invalid_entries;  
	ticket tc = r.tail_counter;
	for (;;)
	{
		ticket hc2 = r.head_counter;  
		size_t nie2 = r.n_invalid_entries;  
		if (hc == hc2 && nie == nie2)
		   break;
		hc = hc2;
		nie = nie2;
		tc = r.tail_counter;
	}
	ptrdiff_t sz = tc-hc-nie;  
	return sz<0 ? 0 :  size_t(sz);  
} [/cpp]

[Alexey-Kukanov]

As far as I can tell, n_invalid_entries is not monotonic. And, there is a timing hole between taking the snapshot and returning the value, so it will remain outdated, even if consistent from implementation point of view. Anyway, thanks for the suggestion; I will pass itto the CQ owner.

[Dmitry_Vyukov]

> As far as I can tell, n_invalid_entries is not monotonic.

I am not sure why I mentioned monotony at all... I think that any consistent snapshot will do.

> And, there is a timing hole between taking the snapshot and returning the value, so it will remain outdated, even if consistent from implementation point of view.

I would not call it outdated. It's a correct value obtained at a serialization point. It's as consistent and fresh as one can get with any queue implementation. Even if a queue is mutex based, one gets the same result - the value can be as if outdated. The "obsoleteness" is inherent to the interface - a user gets what it requests - a queue size at some point time, of course nonzero queue size at some point in time does not mean that try_pop() will succeed in some further point in time.

In the end, it's as outdated as false returned from, for example, try_pop(). So, is try_pop() not thread-safe?

It's not obsoleteness, it's just how the things are in a concurrent environment.

[andysem]

Thanks for your replies, the answer is quite clear to me now. It would be great if Dmitriy's suggestion made it into the library.