[asio] Bug: Handlers execute on the wrong strand.
Hi All, I would like to refer you to this bug report: https://svn.boost.org/trac/boost/ticket/9203 I won't paste the full contents of the bug report into this message. The executive summary is that the allocation algorithm for the implementation of asio::strand can and does allocate the implementation of an existing strand to strands that are subsequently allocated. This can have the effect that handlers wrapped in strand (b) will actually be executed on strand (a). I consider this to be a bug but if there is something that I'm misunderstanding about the operation of strands it would be great if you could help me clear it up. If the consensus is that this is a bug, what are the chances for it to be included in the 1.56 release? It is probably too late to be included in the 1.55 release. I've implemented a work around which could only be described as a hack and would be embarrassed to show it to anybody. But it gets me over my hump :). Thanks! -- Greg
On 23/10/2013 12:56, Quoth Greg Barron:
I would like to refer you to this bug report: https://svn.boost.org/trac/boost/ticket/9203
Interesting. I was recently working on something new that I was hoping to use Asio for but kept running into unacceptably long lock delays (~300ms). The code did make use of parallel jobs on supposedly independent strands so this could have been the culprit.
I've implemented a work around which could only be described as a hack and would be embarrassed to show it to anybody. But it gets me over my hump :).
I actually ended up abandoning Asio and rolling my own threadqueue (I didn't want any of the socket-related stuff so this wasn't as big a job as it sounds). Mine isn't fully-baked yet (and it's Windows-only for the moment) and I'm not sure I'd want to show it off either, but on the upside most of the guts are entirely lock-free (though not wait-free, since it's based on Boost.LockFree's queue).
Greg Barron <gregbarron71 <at> gmail.com> writes:
Hi All,
I would like to refer you to this bug report: https://svn.boost.org/trac/boost/ticket/9203
I won't paste the full contents of the bug report into this message. The executive summary is that the allocation algorithm for the implementation of asio::strand can and does allocate the implementation of an existing strand to strands that are subsequently allocated.
This can have the effect that handlers wrapped in strand (b) will actually be executed on strand (a).
I consider this to be a bug but if there is something that I'm misunderstanding about the operation of strands it would be great if you could help me clear it up.
If the consensus is that this is a bug, what are the chances for it to be included in the 1.56 release? It is probably too late to be included in the 1.55 release.
I've implemented a work around which could only be described as a hack and would be embarrassed to show it to anybody. But it gets me over my hump :).
Thanks!
Out of curiosity, have you tried #define BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION? This allocates the strand implementations in a round-robin fashion rather than relying upon the hash function. For posterity, the strand_service::construct implementation is as follows: void strand_service::construct(strand_service::implementation_type& impl) { boost::asio::detail::mutex::scoped_lock lock(mutex_); std::size_t salt = salt_++; #if defined(BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION) std::size_t index = salt; #else // defined(BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION) std::size_t index = reinterpret_cast<std::size_t>(&impl); index += (reinterpret_cast<std::size_t>(&impl) >> 3); index ^= salt + 0x9e3779b9 + (index << 6) + (index >> 2); #endif // defined(BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION) index = index % num_implementations; if (!implementations_[index].get()) implementations_[index].reset(new strand_impl); impl = implementations_[index].get(); } where salt_ is initialized to 0, and num_implementations is by default 193. The hashing function is pretty standard, using the golden-ratio derived int and the pointer hash which is also implemented the same way in boost.hash. The address of the actual strand is used as the initial index value, hashed via the common pointer hash, then combined with the salt. Effectively I believe this should be the same as using boost.hash on the &impl and then hash_combine with the salt. It seems that using the address of the strand as input may make it feasible to incidentally generate a collision, though I have not seen it in person. But of course, there will always be the possibility of two pointers such that both generate the same eventual hash. My personal use cases generally involve a large amount of strands and the callbacks never block, so the occasional collision is of little consequence. The alternative seems to be using BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION with its caveats, or perhaps investigating alternative hash strategies that does not depend on the address or has better mixing properties. Even randomizing the initial salt_ might help, as the distribution of the indexes seems to improve as it moves from zero, or modifying the salt_ differently than simply incrementing. As an aside, I have also investigated using lock-free and other concurrent data structures and patterns to reduce some locking within asio, and would be interested to see your approach. -Adam D. Walling
On Tue, Oct 22, 2013 at 4:56 PM, Greg Barron <gregbarron71@gmail.com> wrote:
Hi All,
I would like to refer you to this bug report: https://svn.boost.org/trac/boost/ticket/9203
The way I read the test program attached to the ticket: https://svn.boost.org/trac/boost/attachment/ticket/9203/main.cpp, there are only two threads running the continuously posted handlers. And as one of the two threads is blocked in a handler that never returns, a handler posted from the other thread will never get to be executed if it ends up being queued for execution in this blocked thread. I think this is expected behavior as a strand is not supposed to create a new thread behind it and a strand is not linked to a specific thread. It is strange though that, if strands are not being used, the handler posted from the running thread doesn't get to be queued for execution in the blocked thread. This although the behavior should be similar as long as individual operations wrapped in independent strands are equivalent to no strands at all. But, as long as AFAIK there is no documented way of controlling the assignment of handlers and strand-wrapped handlers to running threads, this is in the end an implementation detail. Best regards, Sorin Fetche
Greg Barron <gregbarron71 <at> gmail.com> writes:
Out of curiosity, have you tried #define BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION? This allocates the strand implementations in a round-robin fashion rather than relying upon the hash function.
For posterity, the strand_service::construct implementation is as follows:
void strand_service::construct(strand_service::implementation_type& impl) { boost::asio::detail::mutex::scoped_lock lock(mutex_);
std::size_t salt = salt_++; #if defined(BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION) std::size_t index = salt; #else // defined(BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION) std::size_t index = reinterpret_cast<std::size_t>(&impl); index += (reinterpret_cast<std::size_t>(&impl) >> 3); index ^= salt + 0x9e3779b9 + (index << 6) + (index >> 2); #endif // defined(BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION) index = index % num_implementations;
if (!implementations_[index].get()) implementations_[index].reset(new strand_impl); impl = implementations_[index].get(); }
where salt_ is initialized to 0, and num_implementations is by default
The hashing function is pretty standard, using the golden-ratio derived
int
and the pointer hash which is also implemented the same way in boost.hash. The address of the actual strand is used as the initial index value, hashed via the common pointer hash, then combined with the salt. Effectively I believe this should be the same as using boost.hash on the &impl and then hash_combine with the salt.
It seems that using the address of the strand as input may make it feasible to incidentally generate a collision, though I have not seen it in person. But of course, there will always be the possibility of two pointers such that both generate the same eventual hash.
My personal use cases generally involve a large amount of strands and the callbacks never block, so the occasional collision is of little consequence.
The alternative seems to be using BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION with its caveats, or perhaps investigating alternative hash strategies that does not depend on the address or has better mixing properties. Even randomizing the initial salt_ might help, as the distribution of the indexes seems to improve as it moves from zero, or modifying the salt_ differently than simply incrementing.
As an aside, I have also investigated using lock-free and other concurrent data structures and patterns to reduce some locking within asio, and would be interested to see your approach.
-Adam D. Walling
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Adam, Would you be able to elaborate on the caveats of using BOOST_ASIO_ENABLE_SEQUENTIAL_STRAND_ALLOCATION? My application has recently been encountering collisions with the default hash allocation scheme, resulting in poor concurrency. It seems that sequential allocation would eliminate the collisions, as the application uses less strands than are available per BOOST_ASIO_STRAND_IMPLEMENTATIONS. However, I'm unclear on why hashing is the default to begin with, it seems that sequential would always be better since it gives even distribution. What are the advantages/disadvantages of the two allocation schemes? Thanks, Chris
participants (5)
-
Adam D. Walling -
Chris -
Gavin Lambert -
Greg Barron -
Sorin Fetche