Using Boost.Coroutine to mock threads
Hello folks, I'm currently trying to write tests for some threaded code. However, context switching is not predictable and scheduling is unfair on the platforms concerned, so there is no deterministic behaviour on which I can rely. Here's a sketch of my task_queue class: class task_queue : noncopyable { public: // use num_threads threads to churn through tasks task_queue(unsigned num_threads); // Don't start any new tasks. // Return as soon as all active tasks are complete. ~task_queue(); // throw() // Add a task to the back of the queue void append(const function<void ()> &task); private: // ... }; The tasks should be picked up in FIFO order. Without some kind of deterministic threading implementation, I can't test this with the given interface. To truly test FIFO ordering, looking at when tasks start and/or finish is insufficient. Instead I need to see when a task is picked up by a thread. I can hack in some hooks, but that seems wrong(?). So! I had this slightly wacky thought. Would it be possible to implement the boost.Thread API using Boost.Coroutine? Coroutine yield()s would be performed inside blocking calls to whatever_lock_type::lock(), thread::join(), condition::wait() and so on, perhaps; I haven't completely thought this through, yet... :) If this is possible, I would have a deterministic threading system and therefore have some guarantees to work with in my tests. For example, I can now use the starting time of a task as a measure of the time at which a worker thread plucks a task from the queue (because there would be no context switching between the pluck and the first instruction of the task). Thus, I can test FIFO-ness. I realise Boost.Coroutine isn't an official Boost library, but I'm guessing this is still the best place to find out whether this idea has wings. Hope that's ok. Laugh me off stage if you must! Kind regards, Edd
[Comments below] Edd Dawson wrote:
Hello folks,
I'm currently trying to write tests for some threaded code. However, context switching is not predictable and scheduling is unfair on the platforms concerned, so there is no deterministic behaviour on which I can rely.
Here's a sketch of my task_queue class:
class task_queue : noncopyable { public: // use num_threads threads to churn through tasks task_queue(unsigned num_threads);
// Don't start any new tasks. // Return as soon as all active tasks are complete. ~task_queue(); // throw()
// Add a task to the back of the queue void append(const function<void ()> &task);
private: // ... };
The tasks should be picked up in FIFO order. Without some kind of deterministic threading implementation, I can't test this with the given interface. To truly test FIFO ordering, looking at when tasks start and/or finish is insufficient. Instead I need to see when a task is picked up by a thread. I can hack in some hooks, but that seems wrong(?).
So! I had this slightly wacky thought. Would it be possible to implement the boost.Thread API using Boost.Coroutine? Coroutine yield()s would be performed inside blocking calls to whatever_lock_type::lock(), thread::join(), condition::wait() and so on, perhaps; I haven't completely thought this through, yet... :)
You are entering an extremely interesting area for those of us that are truly test-infected. I've got no comments on the technical feasibility, but for certain testing scenarios the possibility of controlling "thread"-scheduling would definitely be valuable. As a pretty experienced TFD:er with threaded code, I should give you a warning though: the race conditions and deadlock sequences that you are foreseeing, and therefore writing tests for, are generally the ones that you will handle correctly. You should of course be writing tests for those as well as anything else, but there is no real replacement for running "higher-level" unit tests as well with a high amount of contention involved. Such tests are significantly slower than normal unit tests, and might become a real-world annoyance when the amount of unit tests are closing up to several hundreds or even thousands, so your testing tool should have a way of discriminating slow tests for normal compile/link/test cycles. Also, a general recommendataion is to split the code into smaller units whose logic can be separately tested without the involvement of threads before aggregating them into a larger component (as e.g. the task_queue above). What about adding a non-public task_queue_container class that contains enough observer methods to be able to verify the desired behaviour, both in single-threaded and multi-threaded contexts, and letting the public task_queue delegate most of its job to that implementation? All that being said though, I still think your idea is worthwhile pursuing. If you don't get any positive feedback from the Boost community, feel free to e-mail me directly if you ever get any further in this area. Regards, Johan Nilsson
Edd, I think I would second this comment from Johan. Johan Nilsson wrote:
As a pretty experienced TFD:er with threaded code, I should give you a warning though: the race conditions and deadlock sequences that you are foreseeing, and therefore writing tests for, are generally the ones that you will handle correctly. You should of course be writing tests for those as well as anything else, but there is no real replacement for running "higher-level" unit tests as well with a high amount of contention involved.
It isn't just interleaving that you're going to have problems with here. In these days of multi-cores and SMP with non-shared on-core caches you're also looking for visibility problems where a memory write doesn't appear for a thread on another core/processor -- something else you might be able to simulate, but it would be complex too. As Johan says, high level tests will find these, but you need to build high stress environments. Any testing you do where threads aren't on separate cores isn't going to be worth the runtime it takes them to execute either. You also have a number of interesting potential problems due to where objects are placed in memory (i.e. things will be very different if things used by separate threads on different cores happen to be in the same cache line). Using co-routines is an interesting idea, but for the things that they will let you test formal proofs may not be any more work and may give more confidence than testing. I'm sure none of this is stuff you aren't already thinking about though. Kirit -- http://www.kirit.com/
Hi Kirit, Kirit Sælensminde wrote:
It isn't just interleaving that you're going to have problems with here. In these days of multi-cores and SMP with non-shared on-core caches you're also looking for visibility problems where a memory write doesn't appear for a thread on another core/processor -- something else you might be able to simulate, but it would be complex too.
That's an interesting idea, though I currently have absolutely no idea how I'd implement that! I can't see any way of doing it without some of the funkier meta-programming tricks of more dynamic languages. One brain-fart in this general area is that compilers may do different (fewer) kinds of optimisation if threading machinery is detected (AFAIK, this is how pthreads is able to make certain guarantees in conjunction with a compiler). This may have consequences for testing and correctness in general, too. Loads and stores might get moved about by an optimiser looking at coroutine-threaded code causing tests to fail when they'd pass with pre-emptive threading; an assignment may get moved outside a lock()/unlock(), for example. I don't know enough about this area to be able to reason particularly clearly, however.
Using co-routines is an interesting idea, but for the things that they will let you test formal proofs may not be any more work and may give more confidence than testing.
You might be right. But it sounds like too much "fun" not to try :) If successful, it might also stand as a proof of concept for implementing the boost::threads API on systems that don't have pre-emptive threads support, for what it's worth. Edd
Hi Johan, Johan Nilsson wrote:
[Comments below]
Edd Dawson wrote:
So! I had this slightly wacky thought. Would it be possible to implement the boost.Thread API using Boost.Coroutine? Coroutine yield()s would be performed inside blocking calls to whatever_lock_type::lock(), thread::join(), condition::wait() and so on, perhaps; I haven't completely thought this through, yet... :)
You are entering an extremely interesting area for those of us that are truly test-infected. I've got no comments on the technical feasibility, but for certain testing scenarios the possibility of controlling "thread"-scheduling would definitely be valuable.
After experimenting for a few hours yesterday, I'm near certain that this is do-able. I've got enough done this weekend to have rough versions of boost::thread, a couple of the mutexes and boost::barrier to play with. It's encouraging to hear that somebody thinks that there's some value in this. I have to admit that I'm really rather new to methodologies that place a high degree of importance on testing (though I fully agree with the reasoning and have resolved to learn more this year).
As a pretty experienced TFD:er with threaded code, I should give you a warning though: the race conditions and deadlock sequences that you are foreseeing, and therefore writing tests for, are generally the ones that you will handle correctly. You should of course be writing tests for those as well as anything else, but there is no real replacement for running "higher-level" unit tests as well with a high amount of contention involved.
Good point, thank you.
Also, a general recommendataion is to split the code into smaller units whose logic can be separately tested without the involvement of threads before aggregating them into a larger component (as e.g. the task_queue above). What about adding a non-public task_queue_container class that contains enough observer methods to be able to verify the desired behaviour, both in single-threaded and multi-threaded contexts, and letting the public task_queue delegate most of its job to that implementation?
I'm sure that's the correct way to do things but at this early stage in my education I find it hard to see this helping things just yet. I suspect it's probably because I subconsciously want an neat little solution that covers all cases when there probably isn't one. For example, I still couldn't test the FIFO behaviour I require (as far as I can see) without having some kind of cooperative threads implementation. This is my problem, of course and I hope I'll "fix" it with more reading, but I felt I should explain why I didn't find your suggested rearrangement in the first place :)
All that being said though, I still think your idea is worthwhile pursuing.
That's good.
If you don't get any positive feedback from the Boost community, feel free to e-mail me directly if you ever get any further in this area.
Thank you. If I get anywhere useful with this I'll post the code on the web. I know I'll find writing tests for the coroutine-threads a little tricky, so I might come after you for advice on that :) Thanks, Edd
participants (3)
-
Edd Dawson -
Johan Nilsson -
Kirit Sælensminde